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

#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;
}