更好的阅读体验：https://www.luogu.me/article/x6mrfsyu。

#2748. Sam的奇偶树

#树形DP，#树上贪心，#结论

题意

多测。给一棵树，树上节点权值 $a_i \in [0, 2]$。任意地断开边，求最多可以产生多少权值和为 $k$ 的树。要求线性。

我们称满足要求的树为“合法树”。

第一档（30 分）：$n \le 20$

二进制枚举每一条边的状态：0 代表连接，1 代表断开。
对于每一个状态，用并查集维护联通性与权值和。最后打擂得出答案。
认为并查集是常数的，时间复杂度 $\operatorname{O}(n2^{n-1})$。

int T, n, K, a[N], fa[N], siz[N];
pair<int, int> line[N];

int getfa(int x){
	if(fa[x] == x) return x;
	else return fa[x] = getfa(fa[x]);
}

void work(){
	cin >> n >> K;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	for(int i = 1; i < n; i ++){
		int u, v;
		cin >> u >> v;
		line[i] = {u, v};
	}
	int ans = 0;
	for(int s = 0; s < 1<< (n-1); s ++){
		for(int i = 1; i <= n; i ++){
			fa[i] = i;
			siz[i] = a[i];
		}
		for(int i = 0; i <= n-2; i ++){
			if(s>>i&1){
				int u = line[i+1].first, v = line[i+1].second;
				siz[getfa(v)] += siz[getfa(u)];
				fa[getfa(u)] = getfa(v);
			}
		}
		int sum = 0;
		for(int i = 1; i <= n; i ++){
			if(getfa(i) == i){
				if(siz[i] == K) sum++;
			}
		}
		ans = max(ans, sum);
	}
	cout << ans << "\n"; 
}

第二档（60 分）：$n \le 1000$

使用树形 dp。
$f(u, x)$ 代表：u 的子树中，包含 u 的连通块权值和为 x，子树中其余部分最多可以产生多少“合法树”。
设 $u$ 的儿子 $v$。

• 边 $(u, v)$ 如果断开，那么 $f(u, x) \gets f(u, x) + f(v, y) + [y = k]$。
• 如果保持连接，那么 $f(u,x + y) \gets f(u, x) + f(v, y)$。

最终答案为 $\max(f(rt, x) + [x = k])$。

细节：

• $\{ f_{u, x} \}$ 数组同时被调用和修改，需要使用辅助转移数组存储已经合并的信息。
• 设 $sum_u$ 为权值和。$sum_{\text{已合并}} \times sum_{新儿子}$ 相当于将子树内的点两两配对。任意点对只会在 lca 处被配对。一共有 $n^2$ 级别个点对，时间复杂度 $\operatorname{O}(n^2)$。

const int N = 1e3 + 10, inf = 0x3f3f3f3f;
int T, n, K, a[N], sum[N], f[N][2*N], h[2*N];
vector<int> g[N];
void dfs(int u, int fa){//树上背包
	sum[u] = a[u];
	for(int i = 0; i <= 2 * n; i ++) f[u][i] = -inf;
	f[u][a[u]] = 0;
	for(auto v : g[u]){
		if(v == fa) continue;
		dfs(v, u);//先求解v子树
		for(int i = 0; i <= sum[u]; i ++) h[i] = f[u][i];//辅助转移数组
		for(int i = 0; i <= sum[u]; i ++){//已经合并的子树大小
			for(int j = 0; j <= sum[v]; j ++){//新的儿子子树大小
				//连接 u-v
				f[u][i+j] = max(f[u][i+j], h[i] + f[v][j]);
				
				//断开
				f[u][i] = max(f[u][i], h[i] + f[v][j] + (j==K));
			}
		}
		sum[u] += sum[v];
	}
}
void work(){
	cin >> n >> K;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++) g[i].clear();
	for(int i = 1; i < n; i ++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	int ans = 0;
	for(int i = 0; i <= 2 * n; i ++) ans = max(ans, f[1][i] + (i==K));
	cout << ans << "\n";
}

第三档（100 分）：$n \le 10^6$

从下向上贪心，如果以 $u$ 的子树可以产生合法树，则断开 $(u, fa_u)$。

问题转化到“如何判断子树是否可以产生合法树”。

先将 $a_u = 0$ 在逻辑上将其忽略，因为对于权值和没有影响。 设 $sum_u$ 代表以 u 为根的子树的权值和，不包含已经砍掉的部分。

• 若 $k \ge k$ 且 $(sum_u - k) \bmod 2 = 0$，则通过删除权值为 2 和偶数个权值为 1 的叶子节点，一定可以产生合法树。
• 若 $(sum_u - k) \bmod 2 = 1$ 则需要砍去一个权值为奇数的部分。设 $u$ 字数内最小的奇数子树权值和为 $odd_u$。若 $(sum_u - odd_u) \ge k$ 则一定可以产生合法树。

对于第二种情况，$odd_u$ 所代表的子树不能以 $u$ 为根，因为 $u$ 起到了连接不同儿子的作用。

总的算法流程为：

• 从下到上贪心。
• 维护“子树权值和”与“最小奇数子树的权值和”，用于判断是否子树是否可以产生合法树。

注意代码细节。

const int N = 1e6 + 10, inf = 0x3f3f3f3f;
int T, n, K, a[N], ans, sum[N], min_odd[N];
vector<int> g[N];

void dfs(int u, int fa){
	sum[u] = a[u];
	min_odd[u] = inf;
	int cnt_son = 0;
	for(auto v : g[u]){
		if(v == fa) continue;
		cnt_son++;
		dfs(v, u);
		sum[u] += sum[v];
		min_odd[u] = min(min_odd[u], min_odd[v]);
	}
	bool flag = 0;
	if(sum[u] >= K){
		if((sum[u] - K) % 2 == 0)
			flag = 1;
		else if(min_odd[u] != inf && sum[u] - min_odd[u] >= K)
			flag = 1;	
	}
	if(flag){//可以组成一个合法的树，断开 fa - u
		ans++;
		sum[u] = 0, min_odd[u] = inf;
	}else{
		if(min_odd[u] == inf){//儿子中没有奇数子树，则只可能自己是奇数子树
			if(sum[u] % 2 == 1) min_odd[u] = sum[u];
		}
	}
}

void work(){
	cin >> n >> K;
	for(int i = 1; i <= n; i ++) cin >> a[i], g[i].clear();
	for(int i = 1, u, v; i < n; i ++) cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
	ans = 0;
	dfs(1, 0);
	cout << ans << "\n";
}