【MX-S8-T2】配对

为方便描述，称

c_i = 1

的点为黑点，

c_i = 0

的为白点。

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

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

1

个。

然后我们考虑一个点

u

的所有子树，内部的点先匹配完后，剩下的点如何互相匹配。容易想到可以随便匹配，最后如果匹配不完，剩下哪个点也是随便的，因为这些匹配的贡献只和这些子树的根到

u

的路径长度之和相关，而这是个定值。

这样我们或许可以

O(n)

一次 DP 求出固定颜色时的答案了。但原题可以交换颜色，所以我们需要更强的答案求法。

令

sz_u

表示

u

子树中

c_i

的和。我们仔细画一画，发现答案等于所有

sz

为奇数的点到它父节点的边的长度之和。

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

交换两个节点的颜色，它相当于给两个不同颜色的点取反；
如果 $\sum c_i$ 是奇数，我们可以钦定一个不选，相当于给一个黑点取反。

这些全都是取反操作。所以我们设一个 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)

。

具体看代码。

CPP

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

文章操作

相关推荐

评论

【MX-S8-T2】配对