题目链接
做法
考虑只询问 $ 1 $ 号节点怎么做。假如我们选择一个子树然后再选择另一个子树，那么这次操作就抵消了。
对于每一个节点，将它每一个子树的大小计为 $ a_i $ ，然后每次选择 $ a_x, a_y ( a_x > 0, a_y > 0 ) $ ，使 $ –a_x, –a_y $ ，使 $ \sum{a_i} $ 最小。最后有两种情况：
- 当 $ Max ( a_i ) \times 2 >= \sum{a_i} $ ，则该节点子树贡献为 $ Max ( a_i ) \times 2 - \sum{a_i} $ 。
- 否则每次去两个最大值消耗，该节点子树贡献为 $ ( \sum{a_i} ) \mod 2 $ 。
然后就可以在节点不同的儿子中内部抵消，就可以进行树形 DP ，记录一个节点儿子子树消耗后最大值、次大值以及该点子树消耗后的权值。
询问所有点则可以用用类似换根 DP 的方法。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
typedef pair<int, int> pii;
const int N = 100010, INF = 0x3f3f3f3f;
int W, T;
int n, ans[N], dep[N];
vector<int> e[N];
pii f[2][N], a[N];
// f[0][x] > f[1][x]
template<typename T>
inline T Max(const T &x, const T &y) { return x > y ? x : y; }
inline bool operator<(const pii &x, const pii &y) {
return x.fst == y.fst ? x.snd > y.snd : x.fst < y.fst;
}
void dfs1(int u, int ff) {
a[u].fst = 1, dep[u] = dep[ff] + 1;
for(auto v : e[u]) if(v ^ ff) {
dfs1(v, u), a[u].fst += a[v].fst;
if(f[1][u] < a[v]) f[1][u] = a[v];
if(f[1][u] > f[0][u]) swap(f[1][u], f[0][u]);
}
if(f[0][u].fst) {
if(a[u].fst - f[0][u].fst - 1 >= f[0][u].snd + 1)
a[u].snd = (a[u].fst - 1) & 1;
else a[u].snd = f[0][u].snd + 1 - (a[u].fst - f[0][u].fst - 1);
}
else a[u].snd = 0;
}
void dfs2(int u, int ff, pii x) {
pii U = Max(x, f[0][u]); int sz = n - dep[u] + 1;
if(U.fst) {
if(sz - U.fst - 1 >= U.snd + 1) ans[u] = (sz - 1) & 1;
else ans[u] = U.snd + 1 - (sz - U.fst - 1);
}
for(auto v : e[u]) if(v ^ ff) {
if(f[0][u] == a[v]) dfs2(v, u, Max(x, f[1][u]));
else dfs2(v, u, Max(x, f[0][u]));
}
}
int main() {
scanf("%d%d", &W, &T);
for(; T; --T) {
scanf("%d", &n);
for(int i = 1; i <= n; i++)
e[i].clear(), f[0][i] = f[1][i] = a[i] = mp(0, INF);
for(int i = 1, x, y; i < n; i++)
scanf("%d%d", &x, &y), e[x].pb(y), e[y].pb(x);
dfs1(1, 0), dfs2(1, 0, mp(0, INF));
if(W == 3) printf("%d", ans[1] == 0);
else for(int i = 1; i <= n; i++) printf("%d", ans[i] == 0);
puts("");
}
return 0;
}