题解：P14309 【MX-S8-T2】配对
BennyT
·
2025-10-27 14:47:25
·
题解
题解：P14309 【MX-S8-T2】配对
思路
注：本文中黑色节点即为 c_i=1 的节点，白色节点为 c_i=0 的节点。
先考虑没有修改的情况。
如果在以 x 为根的一颗子树内有偶数个黑色节点，则 x 与他的父节点之间的边对答案没有贡献，因为该子树内的黑色节点之间可以两两匹配，这种情况一定比子树内的黑色节点连到外面更优。如果黑色节点个数为奇数，则一定有且仅有一个黑色节点连到子树外的黑色节点，这时需要经过 x 与其父节点的连边一次，所以这条边对答案有贡献。
再考虑修改的情况。
修改中交换两点的颜色实际上是将两点的颜色反转，可以视为将一个黑色节点变白，将一个白色节点变黑。不过还要注意如果一开始黑色节点数量为奇数，我们需要无视一个黑色节点，即多将一个黑色节点变白。
转移方程就比较简单了，输出时当黑色节点总数为奇数时输出 $\min(dp_{rt,1,0},dp_{rt,2,1})$，为偶数时输出 $\min(dp_{rt,0,0},dp_{rt,1,1})$。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,c[1000010],sz[1000010];
ll dp[1000010][3][2],u[1000010][3][2];
struct N{
int y;
ll v;
};
vector<N> e[1000010];
inline ll min(ll a,ll b){return a<b?a:b;}
void dfs(int x,int xfa){
sz[x]=c[x];
dp[x][0][0]=dp[x][c[x]&1][c[x]^1]=0;
for(N i:e[x])if(i.y!=xfa){
int y=i.y,v=i.v;
dfs(y,x);
sz[x]+=sz[y];
for(int i=0;i<=2;i++)for(int j=0;j<=1;j++)u[x][i][j]=1e18;
for(int i1=0;i1<=2;i1++)for(int i2=0;i2<=2;i2++)for(int j1=0;j1<=1;j1++)for(int j2=0;j2<=1;j2++)if(i1+i2<=2&&j1+j2<=1)u[x][i1+i2][j1+j2]=min(u[x][i1+i2][j1+j2],dp[x][i1][j1]+dp[y][i2][j2]+v*((sz[y]-i2+j2+2)&1));
for(int i=0;i<=2;i++)for(int j=0;j<=1;j++)dp[x][i][j]=u[x][i][j];
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>c[i];
for(int i=1,x,y,v;i<n;i++){
cin>>x>>y>>v;
e[x].push_back({y,v});
e[y].push_back({x,v});
}
for(int x=1;x<=n;x++)for(int i=0;i<=2;i++)for(int j=0;j<=1;j++)dp[x][i][j]=1e18;
dfs(1,0);
cout<<((sz[1]&1)?min(dp[1][1][0],dp[1][2][1]):min(dp[1][0][0],dp[1][1][1]));
return 0;
}
```