【LOJ2330】「清华集训 2017」榕树之心

发表于 更新于 本文字数： 2k 阅读时长 ≈ 2 分钟
https://loj.ac/problem/2330

题目链接

「清华集训 2017」榕树之心

做法

考虑只询问 $ 1 $ 号节点怎么做。假如我们选择一个子树然后再选择另一个子树，那么这次操作就抵消了。
对于每一个节点，将它每一个子树的大小计为 $ a_i $ ，然后每次选择 $ a_x, a_y ( a_x > 0, a_y > 0 ) $ ，使 $ –a_x, –a_y $ ，使 $ \sum{a_i} $ 最小。最后有两种情况：

  1. 当 $ Max ( a_i ) \times 2 >= \sum{a_i} $ ，则该节点子树贡献为 $ Max ( a_i ) \times 2 - \sum{a_i} $ 。
  2. 否则每次去两个最大值消耗，该节点子树贡献为 $ ( \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
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
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;
}