2013 ACM区域赛长沙 I LIKE vs CANDLE(ZOJ3734) 很好的一道树形DP

题意：一棵有根树，每个节点都有一个value值和属性（zan或是 CANDLE）。你可以通过反转一些点的属性，反转一个点时候，它的整个子树都会被反转属性。有些点反转消耗代价为X，有些为Y。你的目标的是求zan和candle差的最大值。

思路：dp[i][0]代表zan比candle多的最大值，dp[i][1]代表zan比candle少的最大值。注意每次更新当前节点的状态，如果当祖先节点加上当前节点的反转状态为偶数当然val不变，否则变。此题信息比较多，注意化繁为简。转移方程见代码

 #include<cstdio>

 #include<stack>

 #include<vector>

 #include<map>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int maxn=;

 vector<int>vec[maxn];

 int dp[maxn][];

 int val[maxn],flip[maxn];

 int n,X,Y;

 int u,p;

 int dfs(int t,int st) {

     st+=flip[t];

     if(st&)

         val[t]=-val[t];

     dp[t][]=val[t];

     dp[t][]=-val[t];

     for(int i=; i<vec[t].size(); i++) {

         dfs(vec[t][i],st);

         int v=vec[t][i];

         dp[t][]+=max(dp[v][],dp[v][]-(flip[v]?Y:X));

         dp[t][]+=max(dp[v][],dp[v][]-(flip[v]?Y:X));

     }

 }

 int main() {

 //    freopen("in.txt","r",stdin);

     while(~scanf("%d%d%d",&n,&X,&Y)) {

         for(int i=; i<=n; i++)

             vec[i].clear();

         for(int i=; i<=n; i++) {

             scanf("%d%d%d%d",&val[i],&u,&flip[i],&p);

             vec[u].push_back(i);

             if(p) {

                 val[i]=-val[i];

             }

         }

         dfs(,);

         if(dp[][]<)

             printf("HAHAHAOMG\n");

         else

             printf("%d\n",dp[][]);

     }

     return ;

 }