P9498 题解（2023 激励计划评分 10）

· · 题解

这是 RiOI R2 的 2C 题解。

\text{Subtask} \ 0

直接爆搜。复杂度 \Theta(2^n)。

\text{Subtask} \ 1

把爆搜加上记忆化，或者跑背包。因为值域大小是 \Theta(n^2) 的，所以这里复杂度是 \Theta(n^3) 的。

\text{Subtask} \ 2

不知道有没有针对这个 sub 的做法。

\text{Subtask} \ 3

讲到 \text{Sub} \ 6 的时候再说。

\text{Subtask} \ 4

既然是菊花图，那么有两种情况：

\text{Subtask} \ 5

既然是链，也有两种情况：

\text{Subtask} \ 3\ \&\ 6

考虑树深度序列的性质。

显然的一点，树深度序列排序后，相邻两个差的绝对值不超过 1。换句话说，这玩意值域上是连续的。

\text{Sub} \ 3

先不考虑奇数。我们将排序后的序列两两分组，则每组的两个数之间差的绝对值也不超过 1。

我们从前往后每组每组选，维持当前黑色总和减去白色总和的绝对值在 1 以内。做出一个大胆的猜想：这样最后一定可以回到 0。

具体地，我们维护一个偏移量，表示黑色总和减去白色总和。接下来，我们把所有在一组内的两个数不同的组称为“异值”组。如果当前组内两个数相等，那么我们一黑一白，什么也不用动；剩下来的，都是相邻差为 1 的“异值”，考虑怎么处理它。如果当前的偏移量为 1，说明黑色多。那么我们就要让组内第一个（更小的一个）涂黑，另外一个就是白色。这样我们的偏移量回到了 0。如果偏移量为 -1 同理。如果为 0 怎么办？随便选一个。稍后会证明这样最终偏移量一定能回到 0。

\text{Sub} \ 6

奇数怎么办呢？如果仍然从头开始分组，那么最后一个就很难处理了。俗话说得好，正着不行就倒过来做，我们从后往前分组，最后剩下来的一定是 1，这个是很好处理的。

你可以把它想象为在序列最前面补了一个 0。

正确性证明

对排序后的深度序列模 2 考虑。问题转化为，我们所有的“异值”组个数的奇偶性是不是就是整个序列的和的奇偶性。

一个结论：两个中间没有“异值”组的“异值”组之间的所有和全都是偶数。这是因为，中间被分成了若干偶数组，这些组里面的数两两相同，故恒为偶数。而“异值”中两个数不同，所以和为奇数。奇数乘以奇数得到奇数，乘以偶数得到偶数。于是，“异值”组个数的奇偶性就是整个序列的和的奇偶性。得证。

实现

两种实现方式：一种是 dfs + 排序 \Theta(n\log n)，一种是 bfs \Theta(n)。实际上两者速度差别不大。

dfs:

#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second

using namespace std;

const int maxn = 1e6 + 10;

int n, tot, cur, flag;
vector<int> g[maxn];
pair<int, int> dep[maxn];
int c[maxn];

void dfs(int u, int fa) {
    dep[u] = make_pair(dep[fa].fs + 1, u);
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != fa) dfs(v, u);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    if (n & 1) ++n, flag = true;
    sort(dep + 1, dep + 1 + n);
    for (int i = 1; i <= n; i++) tot += dep[i].fs;
    if (tot & 1) return (puts("-1"), 0);
    for (int i = 1; i <= n; i += 2) {
        if (dep[i].fs == dep[i + 1].fs) c[dep[i].sc] = 0, c[dep[i + 1].sc] = 1;
        else c[dep[i].sc] = cur == -1, c[dep[i + 1].sc] = !c[dep[i].sc], cur = cur != 0 ? 0 : -1;
    }
    for (int i = 1; i <= n - flag; i++) cout << c[i] << " ";
    return 0;
}

bfs:

#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second

using namespace std;

const int maxn = 1e6 + 10;

int n, tot, cur, flag;
vector<int> g[maxn];
int now;
pair<int, int> dep[maxn];
int d[maxn];
int c[maxn];
int vis[maxn];

void bfs(int s) {
    queue<int> que;
    que.push(s);
    vis[s] = true;
    dep[++now] = make_pair(1, s);
    d[s] = 1;
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!vis[v]) {
                que.push(v);
                vis[v] = true;
                dep[++now] = make_pair(d[u] + 1, v);
                d[v] = d[u] + 1;
            }
        }
    }
}

int tn[maxn];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, u, v; i <= n - 1; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    if (n & 1) ++n, ++now, flag = true;
    bfs(1);
    for (int i = 1; i <= n; i++) tot += dep[i].fs;
    if (tot & 1) return (puts("-1"), 0);
    for (int i = 1; i <= n; i += 2) {
        if (dep[i].fs == dep[i + 1].fs) c[dep[i].sc] = 0, c[dep[i + 1].sc] = 1;
        else c[dep[i].sc] = cur == -1, c[dep[i + 1].sc] = !c[dep[i].sc], cur = cur != 0 ? 0 : -1;
    }
    for (int i = 1; i <= n - flag; i++) cout << c[i] << " ";
    return 0;
}