自动搬运

查看原文

来自洛谷，原作者为

	TernaryTree ?steal a life

搬运于2025-08-24 22:48:56，当前版本为作者最后更新于2023-03-01 22:11:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是 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$

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

• 根是菊花的中心

  深度是 $1,2,2,2,\dots$。总和显然为奇数，无解。

• 根不是菊花的中心

  深度是 $1,2,3,3,\dots$。则仅当有奇数个结点时有解，可以对于深度为 $1,2$ 的全选上黑色，然后剩下的都是 $3$，按需分配即可。

$\text{Subtask} \ 5$

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

• 根是链的一端

  链的深度是这样的：$1,2,3,4,\dots$。

  易证得，当 $n\bmod4\in\{1,2\}$ 时总和为奇数而无解。

  从后往前四个四个分组，如果前面不够就补 $0$。然后黑色的选一组中间的，白色的选一组两边的。显然，$i+(i+3)=(i+1)+(i+2)$。

• 根不是链的一端

  大概是这样：$1,2,2,3,3,4,4,5,5,6,7,8,\dots$

  于是对于中间那段出现两次重复的，就一黑一白抵消。对于后面的和深度为 $1$ 的可以参考根是链的一端的情况处理。

$\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;
}