---
url: /algo/kc3o8fxb/index.md
---
比赛链接：https://ac.nowcoder.com/acm/contest/126634

## A. Flower\_Rainbow\_and\_You

根据题意，比较 $a,b,c,d,e,f,g$ 的大小，输出最大所对应的值。

```cpp title="A.cc"
#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s[7] = {"Red", "Orange", "Yellow", "Green", "Blue", "Indigo", "Violet"};
    int st[7];
    for (int i = 0; i < 7; i++)
    {
        cin >> st[i];
    }
    int lst = 0;
    int v = st[0];
    for (int i = 1; i < 7; i++)
    {
        if (st[i] > v)
        {
            lst = i;
            v = st[i];
        }
    }
    cout << s[lst];
    return 0;
}
```

## B. Flower\_Rainbow\_and\_Rhythm

对于每一个 $a\_i$ 判断对 $k$ 求余是否为整数，可以使用 `map<int,int>` 存取。

```cpp title="B.cc"
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> vi(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vi[i];
    }
    map<int, int> mpii;
    for (int i = 0; i < n; i++)
    {
        mpii[vi[i] % k]++;
    }
    for (auto j : mpii)
    {
        if (j.second % 2 != 0)
        {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}
```

## C. Flower\_Rainbow\_and\_Wave

注意到对于长度不是 $1$ 的奇数来说，若长度为 $n$，其可以得到 $k=(n+1)/2$ 的序列 $\[1,2,3,\cdots,k-1,k,k-1,c\cdots,3,2,1]$；而 奇数加奇数等于偶数，所以除了 $2=1+1,4=1+3$ 唯一成立且包含 $1$ 长度的波形来说，不存在，其余的偶数直接使用 $\[1,2,3]+n$ 进行分解即可。

```cpp title="C.cc"
#include <bits/stdc++.h>
using namespace std;
void sol()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << -1;
    }
    else if (n % 2 != 0)
    {
        int k = (n + 1) / 2;
        for (int i = 1; i <= k; i++)
        {
            cout << i << " ";
        }
        for (int i = k - 1; i >= 1; i--)
        {
            cout << i << " ";
        }
    }
    else if (n == 2 || n == 4)
    {
        cout << -1;
    }
    else
    {
        cout << "1 2 1 ";
        int k = (n - 3 + 1) / 2;
        for (int i = 1; i <= k; i++)
        {
            cout << i << " ";
        }
        for (int i = k - 1; i >= 1; i--)
        {
            cout << i << " ";
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        sol();
        cout << "\n";
    }
    return 0;
}
```

## D. Flower\_Rainbow\_and\_Balloon

对于区间 $\[\ell,r]$ 可以获取的最大愉悦值是 $s=\max(R\times 2+Y,Y\times 2+R)+2\times \min(W,m)$，其中

* $R$ 表示红色气球个数
* $Y$ 表示黄色气球个数
* $W$ 表示白色气球个数

注意到 $s$ 随着右端点右移，$R/Y/W$ 都只增不减；左端点右移时只减不增，所以 $s$ 单调；考虑滑动窗口队列，复杂度为 $O(n)$：

1. 左指针 $l = 0$，右指针 $r$ 从 $0$ 扫到 $n-1$;
2. 动态维护窗口内的 $R$、$Y$、$W$
3. 每次右扩后，检查当前窗口是否满足：
   $$
   \max(R\times 2+Y,Y\times 2+R)+2\times \min(W,m)\geqslant k
   $$
4. 如果满足，就尝试移动左指针缩小窗口，同时更新答案

```cpp title="D.cc"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    int n, m;
    ll k;
    cin >> n >> m >> k;
    string s;
    cin >> s;

    ll R = 0, Y = 0, W = 0;
    int l = 0;
    int ans = INT_MAX;

    for (int r = 0; r < n; ++r)
    {
        if (s[r] == 'r')
            R++;
        else if (s[r] == 'y')
            Y++;
        else
            W++;

        while (l <= r)
        {
            ll base0 = 2 * R + Y;
            ll base1 = 2 * Y + R;
            ll base = max(base0, base1);
            ll extra = 2 * min(W, (ll)m);
            ll score = base + extra;

            if (score >= k)
            {
                ans = min(ans, r - l + 1);
                if (s[l] == 'r')
                    R--;
                else if (s[l] == 'y')
                    Y--;
                else
                    W--;
                l++;
            }
            else
            {
                break;
            }
        }
    }

    if (ans == INT_MAX)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        sol();
    }

    return 0;
}
```

## E. Flower\_Rainbow\_and\_Game

由于直接求面对 $2\times 10^5$ 的数据，枚举两个点的距离复杂度 $O(n^2)$ 肯定超时。

设节点个数为 $n$ 对于每相邻的两个节点 $u,v$ 构成的边，如果没有瞬移规则，所有点对的距离和在树上是经典结论：对每一条边 $e$，设去掉它后两边的点数是 $s$ 和 $n-s$，那么这条边对总距离的贡献是 $s\cdot(n-s)$。

把所有边的 $s(n-s)$ 加起来，就是
$$
\text{SumDist}=\sum\_{u\<v}\mathrm{dist}(u,v).
$$
这个用一次 DFS 求子树大小就能算出来。

其次当 $a$ 是 $b$ 的祖先时，原本距离是
$$
\mathrm{dist}(a,b)=\text{depth}\[b]-\text{depth}\[a],
$$
但现在 $\mathrm{rf}(a,b)=1$，也就是说，这一对要从总和里减掉
$$
(\text{depth}\[b]-\text{depth}\[a])- 1.
$$
于是我们需要计算
$$
\text{Reduction}=\sum\_{\substack{a \in Anc(b),\ a\neq b}}
\big(\text{depth}\[b]-\text{depth}\[a]-1\big).
$$
固定一个点 $b$，设它有 $k=\text{depth}\[b]$个祖先（根深度记为 0），这些祖先的深度之和为$\sum \text{depth}\[a]$。那么对这个 $b$ 的贡献是
$$
k\cdot(\text{depth}\[b]-1)- \sum \text{depth}\[a].
$$
在 DFS 从根往下走时，维护两样东西：

* 当前节点的深度 `dep`
* 从根到当前节点所有祖先深度的和 `sumDepAnc`

到达节点 $b$ 时：

* $k = \text{dep}$
* $\sum \text{depth}\[a] = \text{sumDepAnc}$

于是累加
$$
\text{dep}\cdot(\text{dep}-1)- \text{sumDepAnc}.
$$

总的流程为

1. 建树，根设为 1。
2. DFS 一次：
   * 算每个节点的子树大小 `sz[u]`，并用边贡献法累加 `SumDist`。
3. DFS 再一次（或在第一次里顺带）：
   * 维护 `dep` 和 `sumDepAnc`，累加 `Reduction`。
4. 输出 $(\text{SumDist}-\text{Reduction})\bmod 998244353$。

```cpp title="E.cc"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 998244353;

int n;
vector<vector<int>> adj;
vector<int> sz;
ll sd, reduc;

void dfs1(int u, int p)
{
    sz[u] = 1;
    for (int v : adj[u])
    {
        if (v == p)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        ll s = sz[v];
        sd = (sd + s * (n - s)) % MOD;
    }
}

void dfs2(int u, int p, int dep, ll sumDepAnc)
{
    ll c = 1LL * dep * (dep - 1) - sumDepAnc;
    reduc = (reduc + c) % MOD;

    for (int v : adj[u])
    {
        if (v == p)
            continue;
        dfs2(v, u, dep + 1, sumDepAnc + dep);
    }
}
void sol()
{
    cin >> n;
    adj.assign(n + 1, {});
    sz.assign(n + 1, 0);

    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    sd = 0;
    reduc = 0;

    dfs1(1, 0);
    dfs2(1, 0, 0, 0);

    ll ans = (sd - reduc) % MOD;
    if (ans < 0)
        ans += MOD;
    cout << ans << "\n";
}
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        sol();
    }

    return 0;
}
```

## F. Flower\_Rainbow\_and\_Forever

赛时没做出来，但是想出来了，不过有点难构造的，这里仅提出思路：

考虑对所有数字分为 $3$ 类：

* $A$ 表示权值是 $4$ 的倍数；
* $B$ 表示权值是 $u\_B%4=2$；
* $C$ 表示权值是奇数。

贪心地将 $B$ 类连成一条链，剩下 $A,C$ 两类，发现对于有 $n$ 个 $A$ 类节点最多可以连接 $n\_C=(k-1)\times n\_A$ 个。

std：

```cpp title="F.cc"
#include <bits/stdc++.h>
void RainbowDash()
{
    int n, k;
    std ::cin >> n >> k;
    std ::queue<int> A, B, C;
    for (int i = 1; i <= n; i++)
    {
        int x;
        std ::cin >> x;
        if (x % 4 == 0)
            A.push(i);
        else if (x % 2 == 0)
            B.push(i);
        else
            C.push(i);
    }

    if (n == 1)
    {
        std ::cout << "1\n";
        return;
    }

    int root, pre;
    auto print_link = [&]() -> void
    {
        while (A.size())
        {
            std ::cout << pre << ' ' << A.front() << '\n';
            pre = A.front();
            A.pop();
        }
        while (B.size())
        {
            std ::cout << pre << ' ' << B.front() << '\n';
            pre = B.front();
            B.pop();
        }
        return;
    };

    if (C.empty())
    {
        if (!A.empty())
        {
            root = pre = A.front();
            A.pop();
        }
        else
        {
            root = pre = B.front();
            B.pop();
        }

        std ::cout << root << '\n';
        print_link();

        return;
    }

    root = pre = C.front();
    C.pop();

    if (A.empty())
    {
        std ::cout << "-1\n";
        return;
    }

    std ::vector<std ::array<int, 2>> ok;

    bool use = true;
    while (!C.empty())
    {
        if (!C.empty() && A.empty())
        {
            std ::cout << "-1\n";
            return;
        }

        ok.push_back({pre, A.front()});
        pre = A.front();
        A.pop();

        int t;
        use = true;
        for (int i = 1; i <= k; i++)
        {
            if (C.empty())
            {
                use = false;
                break;
            }

            t = C.front();
            ok.push_back({pre, t});
            C.pop();
        }
        if (use)
            pre = t;
    }

    if (use && A.empty() && !B.empty())
    {
        std ::cout << "-1\n";
        return;
    }

    std ::cout << root << '\n';
    for (std ::array<int, 2> &p : ok)
        std ::cout << p[0] << ' ' << p[1] << '\n';
    print_link();

    return;
}

signed main()
{
    std ::ios ::sync_with_stdio(0);
    std ::cin.tie(0);
    std ::cout.tie(0);

    int T = 1;
    std ::cin >> T;
    while (T--)
        RainbowDash();

    return 0;
}
```