题解：P14309 【MX-S8-T2】配对

· · 题解

前言

很史的做法。

解法

我们先不考虑交换操作。

对于 \sum_{i=1}^n c_i 为偶数的情况，一个比较典的东西是：对于每一个点来考虑，如果它的子树内有奇数个 c_i=1 的点，那么则算上它到其父亲的边的代价，否则不需要。

对于 \sum_{i=1}^n c_i 为奇数的情况，一个暴力的做法是，枚举哪个点不和其它点进行匹配，再做一遍上一种情况，这显然是 O(n^2) 的。但是我们发现，使一个点不和其它点匹配，本质上就是把它的 c_i 变成零，因此可以考虑树形 dp，设 f_{i,j} 表示当前考虑到 i 的子树，已经把 j\in\{0,1\} 个一变成了零的所需代价，转移时暴力合并儿子答案，接着再算上自己需要的代价就行了。

再考虑加上交换操作。

发现一次交换操作如果交换两个 c_i 相同的点是无意义的，于是可以等价为把其中一个 c_i=0 的点变成一，并把另外一个 c_i=1 的点变成零，于是考虑延续 \sum_{i=1}^n c_i 为奇数的情况的做法。

我们设 f_{i,j,k} 表示当前考虑到以 i 为根的子树，已经把 j\in\{0,1,2\} 个一变成了零，把 k\in\{0,1\} 个零变成了一的代价，转移方法与上一种情况基本一样。

时间复杂度 O(n)，但是带了十几倍常数。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int c[1000010];
vector<pair<int,int> >v[1000010];
int f[1000010][3][2],sz[1000010],W[1000010],g[3][2];
void dfs1(int x,int fa){
    for(auto pp:v[x]){
        int y=pp.first,w=pp.second;
        if(y==fa)continue;
        W[y]=w;
        dfs1(y,x);
        sz[x]+=sz[y];
        sz[x]%=2;
    }
}
void dfs2(int x,int fa){
    if(v[x].size()==1&&x!=1){
        if(c[x]){
            f[x][0][0]=sz[x]*W[x];
            f[x][1][0]=(!sz[x])*W[x];
            f[x][1][1]=f[x][0][1]=f[x][2][0]=f[x][2][1]=1e18;
        }
        else{
            f[x][0][0]=sz[x]*W[x];
            f[x][0][1]=(!sz[x])*W[x];
            f[x][1][1]=f[x][1][0]=f[x][2][0]=f[x][2][1]=1e18;
        }
        return;
    }
    for(int i=0;i<=2;i++)for(int j=0;j<=1;j++)f[x][i][j]=1e18;
    f[x][0][0]=0;
    for(auto pp:v[x]){
        int y=pp.first,w=pp.second;
        if(y==fa)continue;
        dfs2(y,x);
/*暴力合并子树答案*/
        for(int i=0;i<=2;i++)for(int j=0;j<=1;j++)g[i][j]=f[x][i][j];
        for(int i=0;i<=2;i++){
            for(int j=0;j<=1;j++){
                f[x][i][j]=1e18;
                for(int a=0;a<=i;a++){
                    for(int b=0;b<=j;b++){
                        f[x][i][j]=min(f[x][i][j],g[a][b]+f[y][i-a][j-b]);
                    }
                }
            }
        }
    }
/*算上 x 对答案的贡献*/
    if(c[x]){
        for(int i=2;i>=1;i--){
            for(int j=0;j<=1;j++){
                f[x][i][j]=min(f[x][i][j],f[x][i-1][j]);
            }
        }
    }
    else{
        for(int i=2;i>=0;i--){
            f[x][i][1]=min(f[x][i][1],f[x][i][0]);
        }
    }
    for(int i=0;i<=2;i++){
        for(int j=0;j<=1;j++){
            f[x][i][j]+=(sz[x]^((i+j)%2))*W[x];
        }
    }
}
inline int read(){
    int x=0;
    char ch=getchar_unlocked();
    while(!isdigit(ch))ch=getchar_unlocked();
    while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar_unlocked();
    return x;
}

signed main(){
    int n=read();
    for(int i=1;i<=n;i++){
        c[i]=read();
        sz[i]=c[i];
    }
    for(int i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    dfs1(1,0);
    dfs2(1,0);
    if(sz[1]%2==0){
        cout<<min(f[1][1][1],f[1][0][0]);
    }
    else{
        cout<<min(f[1][2][1],f[1][1][0]);
    }
    return 0;
}