ZOJ 3734 LIKE vs CANDLE

　　题目意思：(13年长沙站的一道水DP,本人也去了，当时太水笔) 说俩个人竞争选票，每个人可以随机选择支持谁。每个人带有权重不同。

现在已经结束了投票阶段，你一个骇客 支持LIKE  你写了一个软件可以 用LIKE 的 X点能量翻转某个个节点，这个节点的儿子也一样跟着翻转（转自他的就是他的儿子，孙子也一样，支持的人变了）；

　　有的点已经被人用   同样   的方法翻转过。这样的先需用Y能量，问LIKE-CANDLE最大和最小值：

　　解法：对于每个节点最多一次操作，对吧，不解释；所以DP[num][flag]//代表LIKE-CANDLE最大和最小值：

多以我们只要维护俩个值支持LINK-CANDLE就可以了；

　　代码注释如下：

#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int maxn=;
struct Edge
{
    int to,pre;
    Edge(int to=,int pre=):to(to),pre(pre){}
};
Edge edge[maxn<<];
int head[maxn],pos;
int val[maxn];
int used[maxn];
int suport[maxn];
int n,x,y;
int dp[maxn][];
void inint()
{
    memset(head,-,sizeof(head));
    pos=;
}
void add_edge(int s,int to)
{
    edge[pos]=Edge(to,head[s]);
    head[s]=pos++;
}
void dfs(int s,int cnt)
{    int ans,key;
    if(used[s])cnt++;
    if( ((cnt&) && (suport[s]==)||( !(cnt&) &&(suport[s]==)  ) ))
    {
        dp[s][]=val[s];
        dp[s][]=-val[s];
    }
    else
    {
        dp[s][]=-val[s];
        dp[s][]=val[s];
    }//上面是初始化初始的权值
    for(int i=head[s];~i;i=edge[i].pre)
    {
        Edge &tmp=edge[i];
        dfs(tmp.to,cnt);
        dp[s][]+=dp[tmp.to][];
        dp[s][]+=dp[tmp.to][];
    }
　　//这是整棵树的最大最小
    if(s)
    {
        int need;
        if(used[s])need=y;
        else       need=x;
        dp[s][]=max(dp[s][],dp[s][]-need);
        dp[s][]=max(dp[s][],dp[s][]-need);
    }
　　//中是否翻转后的最大和最小
}
int main()
{
    int s;
    while(~scanf("%d%d%d",&n,&x,&y))
    {
        inint();
        for(int i=;i<=n;i++)
        {
            scanf("%d%d%d%d",&val[i],&s,&used[i],&suport[i]);
            add_edge(s,i);
        }
        dfs(,);
        if(dp[][]>=) printf("%d\n",dp[][]);
        else puts("HAHAHAOMG");
    }
    return ;
}