看完一篇题解后，我觉得自己写一篇题解，以保证理解度。 很显然，我是没有实力独自做出这道题的。

#2748 Sam的奇偶树题解

30分解法

对于 $1 \le n \le 20$ 的部分，时间复杂度大约 $O(2^n)$，可以暴力枚举每一条边是否删除，然后把所有子树收集上来。

60分解法

对于 $1 \le n \le 1000$ 的部分，考虑二维dp，因为需要统计跨子树答案。 $dp[u][s]=[\text{在u的子树内，存在一个累加和为s的连通快包含u}]$ PS: $[P]$在 C++ 中可以理解为 int(P) （其中 P 是 bool类型）

但这样转移是 $O(n^3)$ 的，需要进行优化。 在树上优化二维 dp 的常用的是 size 优化，而因为 $a_i \in [0, 2]$，所以一个子树的$\sum{a_i} \le \text{子树的大小} \times 2$ 所以可以使用 size 优化。 关于size优化是什么，南外的 S+ 课程讲过，就不做过多的说明了。

100分解法

观察重要性质 $a_i \in [0, 2]$。 可以推导出若存在一棵子树的累计和不小于 $k$，且奇偶性与 $k$ 相同，则一定有一个权值和为 $k$ 的连通快。

证： 若有 $S = \sum_{i \in subtree(u)}{a_i}$， 且 $S \equiv k \pmod{2}$ 若 $S > k$，则一定有 $S \ge k + 2$

• 若有 $a_i = 0$ 的叶子节点，则删除该叶子节点，累加和不变。
• 若有 $a_i = 2$ 的叶子节点，则删除该叶子节点，累计和减少 $2$
• 若同时不满足上面两个情况，则一定有至少两个 $a_i = 1$ 的叶子节点，同时删除后累计和减少 $2$

递归此过程，直到 $S = k$ 为止。 证毕。

令 $dp[u][s]$ 表示 $u$ 为根的子树，累计和$\mod 2 \equiv s$，在尽量多构造的前提下，最大包含 $u$ 的连通快的累计和是多少。 若 dfs 返回了 $true$ 则说明 $u$ 已经被用了构造 $\sum{a_i}= k$ 的子树了，则无法使用 $u$ 的 dp 值。

贪心选择尽量低的子树进行构造，最小化影响上面的结果。

100分代码

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr size_t N = 1000005;
int t, n, k;
int a[N];
int head[N], nxt[N << 1], to[N << 1], cntg;
int dp[N][2], tmp[2];
int res;
void addEdge(int u, int v)
{
    nxt[++cntg] = head[u];
    to[cntg] = v;
    head[u] = cntg;
}
bool dfs(int u, int f)
{
    dp[u][a[u] & 1] = a[u];
    for (int e = head[u]; e > 0; e = nxt[e])
    {
        int v = to[e];
        if (v != f)
        {
            if (dfs(v, u)) continue;
            memcpy(tmp, dp[u], sizeof(tmp));
            for (int i = 0; i < 2; i++)
            {
                if (dp[u][i] == -1) continue;
                for (int j = 0; j < 2; j++)
                {
                    if (dp[v][j] == -1) continue;
                    tmp[i ^ j] = max(tmp[i ^ j], dp[u][i] + dp[v][j]);
                }
            }
            memcpy(dp[u], tmp, sizeof(tmp));
        }
    }
    if (dp[u][k & 1] >= k)
    {
        res++;
        return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    cin >> t;
    int u, v;
    while (t--)
    {
        cin >> n >> k;
        cntg = res = 0;
        for (int i = 1; i <= n; i++)
        {
            head[i] = 0;
            dp[i][0] = dp[i][1] = -1;
            cin >> a[i];
        }
        for (int i = 1; i < n; i++)
        {
            cin >> u >> v;
            addEdge(u, v);
            addEdge(v, u);
        }
        dfs(1, 0);
        cout << res << '\n';
    }
    return 0;
}

Sweet Sugar

题目链接： Sweet Sugar 。

题目描述：

一颗 $n$ 个点的树，每个点有点权 $a_i$ ，求将树划分为若干个连通子图后点权和为 $k$ 的子图的个数的最大值。

$a_i\in\{0,1,2\},n,k\le 10^6$ 。

$60$ 分是显然的树形 DP 。

考虑最终的最优解的结构是什么。我们发现，当一个子树可以凑成长度为 $k$ 的子图时，我们必然应该把它划分为一个连通子图。这是它为上级贡献是没有意义的。

所以我们可以得出如下伪代码：

DFS(x):
something <- 0
for u in son[x]:
  DFS(u)
  ADD(x,u)
if(Can_Get_K(x))
  ans++
  DELETE(x)

重点就在如何判断一个子树是否能拼成一个 $k$ 的连通子图。

由于点权只有 $0,1,2$ ，所以考虑奇偶性相关。经过观察，我们发现如下性质：

• 如果一个子树满足它内部所有子树都不能拼出 $k$ ，且其可以拼出 $\ge k$ 的连通子图并且这个联通子图的权值和 $s$ 满足 $s \equiv k\pmod 2$ ，则这个子图可以拼出 $k$ 的连通子图。

证明：

删掉叶子 $0$ 没有意义。删掉叶子 $2$ 可以在不改变奇偶性的情况下进行减法。删掉叶子 $1$ 有一点复杂：

• 如果有 $2$ 个 $1$ 叶子，则也可以实现和 $2$ 一样的效果。
• 如果只有 $1$ 个 $1$ 叶子，此时考虑去掉所有其他的 $0,2$ 叶子的情况下子树仍然不能恰好为 $k$ 。此时形态必然为链。那么这种情况下就不满足 一个子树满足它内部所有子树都不能拼出 k 的限制了，这一点可以通过调整法证明。

于是我们就证明了了。

由此，定义 $f_{i,j}$ 表示子树 $i$ ，能拼出奇偶性为 $j$ 的最大值。转移十分显然。最终 Can_Get_K(x) 只需要判断 f[i][k&1]>=k 是否成立即可。

代码十分简单，不放了。

直接暴力枚举所有连通块可以获得 $30$ 分。

$60$ 分给到一些 $O(n^2)$ 的优化做法。

那么考虑如何解决满分，本题需要关注到一个关键信息：节点只有 $0,1,2$。

那么考虑以某个节点 $x$ 为根的子树当做一个连通块来看待。

如果这个连通块的点数总和为 $sum[x]$，首先我们可以直接将联通块周围的 $0$ 全部删除，不影响结构和计算。

然后会发现如果 $sum[x]<=2$，那么这棵树只有三种情况：$1,1+1,2$，那么直接根据需求删点即可。

如果 $sum[x]>2$，那么这个联通块必然存在至少两个叶子，而叶子要么是 $1$ 要么是 $2$，也就是意味着，我们一定可以让 $sum[x]$ 变为 $sum[x]-2$，然后就可以递归向下考虑，可以一直 $-2$。

所以如果 $sum[x] - k$ 是偶数，显然就可以直接将 $x$ 和父亲断开，$x$ 以下直接成为一个符合要求的连通块。

那么考虑如果 $sum[x]-k$ 是奇数，那么很显然我们只要想办法减掉一个奇数，就会变成上面这种情况，那为了尽量能保证减完以后还能满足条件，我们肯定是减去一个尽可能小的奇数，那我们就在 $x$ 的子树里挑选一个尽可能小的奇数子树删除即可。

那么我们就可以遍历这棵树，在递归的过程中顺便求出子树的节点和以及子树里最小的奇子树权值和，每次贪心的判断当前节点 $u$ 能否成为一个满足条件的连通块，如果可以就直接断开 $u-fa$，成为一个合法的连通块。

整体复杂度即为 $O(n)$ 。

60pts

记 $f_{i, j}$ 表示 $i$ 的连通块 $j$ 的权值和。 $f_{i, k+x} = f_{i, k} + f_{son, x}$,其中 $k+x \le K$。$K$ 是要求的权值和。

反之 $f_{i, k} = f_{i, k} + f_{son, x} + [x=K]$。

答案显然，初始显然。

const int N = 4e3;
int a[N],dp[1005][2010] , sz[N], pre[2010]; 	
vector<int> tr[N] ;
int n, k;
void dfs1(int idx, int fa)
{
	sz[idx] = a[idx] ;
	for(int j=0;j<=2*n;j++) dp[idx][j] = -999999999; 
	dp[idx][a[idx]] = 0;
	for(int i : tr[idx])
	{
		if(i == fa) continue ;
		dfs1(i, idx);
		for(int j=0;j<=sz[idx];++j)
		{
			pre[j] = dp[idx][j] ;
			dp[idx][j] = -999999999;
		}
	
		for(int j=0;j<=sz[idx];++j)
		{
			for(int p=0;p<=sz[i];++p)
			{
				// link!
				dp[idx][j+p] = max(dp[idx][j+p], pre[j] + dp[i][p]) ;
				dp[idx][j] = max(dp[idx][j], pre[j] + dp[i][p] + (p == k)) ; 
			}
		}
		sz[idx] += sz[i] ;
	}
}

	for(int p=0;p<=2*n;p++)
		{
			ans = max(ans, (p==k) + dp[1][p]) ;
		}

T4

$O(n^2)$ 的 dp 是显然的。

考虑优化：

DP 优化： DS,MATH,找性质

我们显然无法使用前两个，考虑找性质。

得出结论：

甲：从下而上，能分则分，必然不劣。

证明显然，没有用到 $a_i \in {0,1,2}$。

乙：若有一个连通块 $E$，他能表示的最大的奇数，偶数分别为 $(a, b)$。则对于 $k$ ，若 k 是奇数，$k \le a$, 反之 $k \le b$。这是 $k$ 可以被连通块割裂出来。

证明不显然。

证明：对于 $E$，若权值和 $\ge 2$，则 $E$ 的度为 $0$ 的点，至少两个。

考虑只有两个，若这两个点存在 $0,2$ 直接断掉就行。奇偶性不变。

反之，则将两者断掉，奇偶性均不变。

故原命题成立。

于是维护 $h_{i,0/1}$ 表示以 $i$ 为 根，权值和奇偶性为 $0/1$，的最大权和。（若 $i$ 被割裂，为 $-\inf$）。

转移显然，注意初始状态的设计。

更好的阅读体验：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";
}