题意:给你一颗树然后，树上的点有权值1,0,-1，-1可以换成0或者1，然后每条变连接的两个点权值如果不一样那么答案加一，让你求把1怎么变使得最后的答案最小
题解:树形dp,分为几种情况如果树上的权值
如果为0的话转移方程为：dp[0][u] += min(dp[1][v]+1,dp[0][v]),
如果为1的话转移方程为：dp[1][u] += min(dp[1][v],dp[0][v]+1)，
如果为-1的话转移方程为：dp[0][u] += min(dp[1][v]+1,dp[0][v])；
dp[1][u] += min(dp[1][v],dp[0][v]+1)
其中u为树结点的编号，v为该结点的孩子编号
最后答案即min(dp[1][1],dp[0][1])
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cstdio> #include<cmath> #include<set> #include<map> #include<cstdlib> #include<ctime> #include<stack> using namespace std; #define mes(a) memset(a,0,sizeof(a)) #define rep(i,a,b) for(i = a; i <= b; i++) #define dec(i,a,b) for(i = b; i >= a; i--) #define fi first #define se second #define ls rt<<1 #define rs rt<<1|1 #define mid (L+R)/2 #define lson ls,L,mid #define rson rs,mid+1,R typedef double db; typedef long long int ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int mx = 1e5+5; const int inf = 1e6; const int x_move[] = {1,-1,0,0,1,1,-1,-1}; const int y_move[] = {0,0,1,-1,1,-1,1,-1}; int n,m; vector<int>g[mx]; int a[mx]; int dp[2][mx]; void dfs(int u,int fa){ if(a[u]==-1) dp[0][u] = dp[1][u] = 0; else dp[a[u]][u] = 0; for(auto v: g[u]){ if(v!=fa){ dfs(v,u); if(a[u]==-1){ dp[0][u] += min(dp[0][v],dp[1][v]+1); dp[1][u] += min(dp[0][v]+1,dp[1][v]); } else dp[a[u]][u] += min(dp[a[u]][v],dp[a[u]^1][v]+1); } } } int main(){ int t,q,ca = 1; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); dp[0][i] = dp[1][i] = inf; g[i].clear(); } for(int i = 1; i < n; i++){ int u,v; scanf("%d%d",&u,&v); g[u].push_back(v); g[v].push_back(u); } dfs(1,1); printf("%d\n",min(dp[0][1],dp[1][1])); } return 0; }