题意：有n个人，他们的关系，形成一棵有根树（0是树根，代表管理员），每个人有一个价值
现在有一条微博，每个人要么点赞，要么送一个蜡烛
初始一些人利用bug反转了某些人的操作（赞变蜡烛 或者 蜡烛变成赞）
每当一个人被被反转，那么他的子树跟着反转，即一次反转一棵子树
现在你是管理员，你可以反转这些人的操作，反转次数任意次，
每次反转的代价分两种情况，如果这个人初始通过bug被反转过，代价是Y，否则是X
现在问你作为管理员，如何反转，使得 点赞的人价值总和 - 送蜡烛的人价值总和 最大
输入： 先是n个人，然后代价X，代价Y，然后之后又n行，每一行4个数，代表这个人的价值，他的父节点的人，
初始是否被bug反转过（1表示有，0没有），初始是什么操作（0表示点赞，1表示送蜡烛）
分析：树形dp 对于每个节点 i dp[i][0]表示当前子树，赞的总价值-蜡烛总价值 的最大值
dp[i][1]表示当前子树，蜡烛总价值-赞的总价值 的最大值
然后更新的时候，dp[i][0]=v[i]+max(dp[j][0],dp[j][1]-(fiip[j]?Y:X)) j表示i子树
子树最优有两种情况，dp[j][0]，或则由，dp[j][1]反转，减去Y或者X的代价
dp[i][1]是一样的
代码：
#include#include #include #include #include #include #include using namespace std;typedef long long LL;const int N=5e4+5;const int INF=0x3f3f3f3f;struct Edge{ int v,next;}edge[N];int head[N],tot,dp[N][2],val[N],n,flip[N];int X,Y;void add(int u,int v){ edge[tot].v=v; edge[tot].next=head[u]; head[u]=tot++;}void dfs(int u,int cur){ if(flip[u])cur^=1; if(cur)val[u]=-val[u]; dp[u][0]=val[u],dp[u][1]=-val[u]; for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; dfs(v,cur); dp[u][0]+=max(dp[v][0],dp[v][1]-(flip[v]?Y:X)); dp[u][1]+=max(dp[v][1],dp[v][0]-(flip[v]?Y:X)); }}int main(){ while(~scanf("%d%d%d",&n,&X,&Y)){ for(int i=0;i<=n;++i)head[i]=-1; tot=0; for(int i=1;i<=n;++i){ int f,tp; scanf("%d%d%d%d",&val[i],&f,&flip[i],&tp); if(tp)val[i]=-val[i]; add(f,i); } dfs(0,0); if(dp[0][0]<0)printf("HAHAHAOMG\n"); else printf("%d\n",dp[0][0]); } return 0;}