2023天梯赛L3-2 完美树

题意：

给定一颗树，每个节点颜色为0，或1，0代表黑色，1代表白色。每个点可以花费 w i w_i wi​的代价改变颜色，求将整棵树中黑色节点数量与白色节点数量相差不超过1的最小代价。

思路：

裸的树$dp$，我们定义：
$dp[i][0]:$以$i$为根的子树中0、1节点数量相等
$dp[i][1]:$以$i$为根的子树中0节点数量大于1
$dp[i][2]:$以$i$为根的子树中0节点数量小于1
显然，只有子树大小为偶数时$dp[i][0]$才有意义，为奇数时$dp[i][1,2]才有意义$。
考虑转移：
令$sz[u]$为以$u$为根的子树大小
对于当前点$u$，其子节点$son$，若$sz[u]$为偶数，那么直接将$dp[son][0]$转移。若为奇数，我们需要讨论。
假设有$cnt$个子树大小为奇数的$son$。
若$cnt$为奇数，那么说明$sz[u]$是偶数，我们只需考虑计算$f[u][0]$。
若$color[u]=0$,那么我们可以选择 c n t 2 + 1 \\frac{cnt}{2} + 1 2cnt​+1个 f [ s o n ] [ 1 ] , c n t 2 个 f [ s o n ] [ 2 ] f[son][1],\\frac{cnt}{2}个f[son][2] f[son][1],2cnt​个f[son][2]，这样加上$u$的颜色,0和1数量相等。
反之，若$color[u]=1$，那么我们可以选择 c n t 2 + 1 \\frac{cnt}{2} + 1 2cnt​+1个 f [ s o n ] [ 2 ] , c n t 2 个 f [ s o n ] [ 1 ] f[son][2],\\frac{cnt}{2}个f[son][1] f[son][2],2cnt​个f[son][1].
若$cnt$为偶数，则$sz[u]$为奇数，我们考虑转移$f[u][1,2]$。
我们可以选择 c n t 2 个 f [ s o n ] [ 1 ] , c n t 2 个 f [ s o n ] [ 2 ] \\frac{cnt}{2}个f[son][1],\\frac{cnt}{2}个f[son][2] 2cnt​个f[son][1],2cnt​个f[son][2]，此时$color[u]=0$或者$color[u]=1$都可以。
或者选择 c n t 2 − 1 \\frac{cnt}{2}-1 2cnt​−1个$f[son][1]$, c n t 2 + 1 \\frac{cnt}{2}+1 2cnt​+1个$f[son][2]$，此时$color[u]=0$
或者选择 c n t 2 − 1 \\frac{cnt}{2}-1 2cnt​−1个$f[son][2]$, c n t 2 + 1 \\frac{cnt}{2}+1 2cnt​+1个$f[son][1]$，此时$color[u]=1$

还有一个问题是假如我们选了$a$个$f[son][1]$, $cnt-a$个$f[son][2]$，如何选使总代价最小。
令总代价 s u m = a ∗ f [ s o n ] [ 1 ] + ( c n t − a ) ∗ f [ s o n ] [ 2 ] = a ∗ ( f [ s o n ] [ 1 ] − f [ s o n ] [ 2 ] ) + c n t ∗ f [ s o n ] [ 2 ] \\begin{aligned} sum &= a*f[son][1]+(cnt-a)*f[son][2] \\\\ &=a*(f[son][1]-f[son][2])+cnt*f[son][2] \\end{aligned} sum​=a∗f[son][1]+(cnt−a)∗f[son][2]=a∗(f[son][1]−f[son][2])+cnt∗f[son][2]​
那么我们根据选择$f[son][1]$的个数维护前几个$f[son][1]-f[son][2]$即可，可以看代码如何实现。

const int N = 1e5 + 50;
const int M = N << 1;
const int mod = 1e9 + 7;int h[N], e[M], ne[M], idx;
int n, color[N], w[N], fa[N];
int f[N][3], sz[N];void add(int a, int b) {e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}
void dfs(int u) {sz[u] = 1;int cnt = 0, sum0 = 0, sum2 = 0;vector<int> q;for(int i = h[u]; ~i; i = ne[i]) {int j = e[i];dfs(j);sz[u] += sz[j];if(sz[j] & 1) {cnt++;sum2 += f[j][2];q.push_back(f[j][1] - f[j][2]);} else {sum0 += f[j][0];}}sort(q.begin(), q.end());int len = q.size();if(cnt == 0) { f[u][1] = sum0 + (color[u] == 0 ? 0 : w[u]);f[u][2] = sum0 + (color[u] == 1 ? 0 : w[u]);} else if(cnt & 1) {int now = 0;for(int i = 0; i < len / 2; i++) now += q[i];if(color[u] == 0) f[u][0] = sum0 + sum2 + min(now, now + w[u] + q[len / 2]);else f[u][0] = sum0 + sum2 + min(now + q[len / 2], now + w[u]);} else {int now = 0;for(int i = 0; i < len / 2; i++) now += q[i];if(color[u] == 1) {f[u][1] = min(now + w[u], now + q[len / 2]) + sum0 + sum2;f[u][2] = min(now, w[u] + now - q[len / 2 - 1]) + sum0 + sum2;} else {f[u][1] = min(now, now + q[len / 2] + w[u]) + sum0 + sum2;f[u][2] = min(now + w[u], now - q[len / 2 - 1]) + sum0 + sum2;}}
}signed main() {
#ifdef JANGYIfreopen("input.in", "r", stdin);freopen("out.out", "w", stdout);
#endifios::sync_with_stdio(false);cin.tie(0); memset(h, -1, sizeof h);cin >> n;for(int i = 1; i <= n; i++) {int c, p, k;cin >> c >> p >> k;color[i] = c;w[i] = p;while(k--) {int x; cin >> x;add(i, x);fa[x] = i;}}int root = 1;while(root <= n && fa[root]) ++root;dfs(root);if(n & 1) cout << min(f[root][1], f[root][2]);else cout << f[root][0];return 0;
}
/*
f[i][0]:0=1
f[i][1]:0>1
f[i][2]:0<1
*/