思路就是树d,大概是change里面写错了
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
int cnt,head[N];
int dp[N][2];
int n,a[N],b[N];
int mean[N];//本来就是有意义的
int a_i[N];//每个员工的初始反馈
struct edge{
int next,to;
}e[N];
void add_edge(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int change(int u,int fa,int cd,int son){//son为儿子个数
vector<int> va;
int w=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
va.push_back(dp[v][cd^1]);
}
sort(va.begin(),va.end());
for(int i=0;i<son/2;i++){
w+=va[i];
}
//if(cd==a[u]) w+=b[u];//自己也要加上
return w;
}
int dfs(int u,int fa){
int solve=0,son=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
solve+=dfs(v,u);
son++;
}
if(solve!=son/2){//意见不平衡
if(solve>son/2){//同意
//cout<<"u: "<<u<<" "<<1<<endl;
dp[u][1]=0;
dp[u][0]=change(u,fa,1,son);//需要改变其中的1
return a_i[u]=1;
}
else {//不同意
//cout<<"u: "<<u<<" "<<0<<endl;
dp[u][0]=0;
dp[u][1]=change(u,fa,0,son);//改变其中的0
return a_i[u]=0;
}
}
else{//意见平衡 ,也就是说本来就是有意义的
//cout<<u<<endl;
mean[u]=1;//本来就有意义的点
dp[u][a[u]]=0;//自己的意见就是反馈
dp[u][a[u]^1]=b[u];//可以改变自己的意见
return a_i[u]=a[u];//返回自己的意见
}
}
signed main(){
freopen("vote.in","r",stdin);
freopen("vote.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
int v;
cin>>v>>a[i]>>b[i];
add_edge(i,v);
add_edge(v,i);
}
dfs(1,0);
for(int i=1;i<=n;i++){
//cout<<"反馈: "<<a_i[i]<<endl;
if(mean[i]) {
cout<<0<<endl;
continue;
}
cout<<dp[i][a_i[i]^1]<<endl;
}
return 0;
}