【MX-S8-T2】配对

· · 题解

为方便描述，称 c_i = 1 的点为黑点， c_i = 0 的为白点。

以下为我赛时的思考路径：

首先可以发现，一颗子树中的所有黑点肯定需要尽量匹配，最多剩下 1 个。

然后我们考虑一个点 u 的所有子树，内部的点先匹配完后，剩下的点如何互相匹配。容易想到可以随便匹配，最后如果匹配不完，剩下哪个点也是随便的，因为这些匹配的贡献只和这些子树的根到 u 的路径长度之和相关，而这是个定值。

这样我们或许可以 O(n) 一次 DP 求出固定颜色时的答案了。但原题可以交换颜色，所以我们需要更强的答案求法。

令 sz_u 表示 u 子树中 c_i 的和。我们仔细画一画，发现答案等于 所有 sz 为奇数的点到它父节点的边的长度之和。

现在我们需要最小化这个东西。我们可以做什么：

这些全都是取反操作。所以我们设一个 DP，令 f_{i,x,y} 表示在 i 的子树中，取反 x 个黑点，y 个白点，最小的答案。

转移根据每个子树的奇偶性算贡献。 最终答案，钦定 1 是根，如果 \sum c_i 是奇数就是 \min(f_{1,1,0},f_{1,2,1}) ，偶数就是 \min(f_{1,0,0},f_{1,1,1}) ，复杂度 O(n)。

具体看代码。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;

struct node{
    int to,w;
};

vector <node> G[N];
int n,c[N],f[N][3][2],g[N][3][2],sz[N],sum[N];

void dfs(int u,int fa){
    sz[u] = c[u];
    for(auto v : G[u]){
        int to = v.to;
        if(to == fa) continue;
        dfs(to,u);sz[u] += sz[to];
    }
}

void dp(int u,int fa){
    f[u][0][0] = 0;
    if(c[u]) f[u][1][0] = 0;
    else f[u][0][1] = 0;

    for(auto v : G[u]){
        int to = v.to,w = v.w;
        if(to == fa) continue;
        dp(to,u);
        memset(g[u],0x3f,sizeof(g[u]));
        for(int p1 = 0;p1 <= 2;p1 ++){
            for(int q1 = 0;q1 <= 1;q1 ++){
                for(int p2 = 0;p2 <= 2;p2 ++){
                    for(int q2 = 0;q2 <= 1;q2 ++){
                        int x = p1 + p2,y = q1 + q2;
                        if(x > 2 || y > 1) continue;
                        g[u][x][y] = min(g[u][x][y],
                        f[to][p2][q2] + f[u][p1][q1]
                                         + w * ((sz[to] + p2 + q2) % 2 == 1));
                    }
                }
            }
        }
        memcpy(f[u],g[u],sizeof(g[u]));
    }
}

signed main(){

    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> c[i];
    for(int i = 1;i < n;i ++){
        int u,v,w;cin >> u >> v >> w;
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs(1,0);
    memset(f,0x3f,sizeof(f));

    dp(1,0);

    if(sz[1] % 2 == 0) cout << min(f[1][0][0],f[1][1][1]);
    else cout << min(f[1][1][0],f[1][2][1]);

    return 0;
}