树形DP(2)-Hdu 4799 LIKE vs CANDLE

本文主要是介绍树形DP(2)-Hdu 4799 LIKE vs CANDLE，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：2013长沙赛区区域赛题目 http://acm.hdu.edu.cn/showproblem.php?pid=4799

Description

A microblog caused a war recently - There's the war between LIKE and CANDLE.

As you see, there are N accounts are trying to show their support of LIKE or CANDLE. The way they show the support is forwarding a microblog, which means you choose someone's microblog and repost it with some comment. A valid support microblog is forwarding the original account's microblog or a other valid support microblog. We can assume that all accounts will forward the microblog only once. Also, it is impossible for a microblog forwarding a microblog that posts after it.

When the activity ends, someone will use a software to check these accounts and calculate a Power Point for LIKE and CANDLE. Specifically, each account will have a value based on some algorithm (you need not to care). The value will be added to LIKE if the account is voting LIKE, vice versa. So easy, isn't it?

Edward is a programmer and he supports LIKE. He found a bug in the software that used in the activity - He can spend XPower Point of LIKE to flip an account. When an account is flipped, it will be seen as it votes the other side. For example, if Alice votes LIKE and then it is flipped, the software will add the value to CANDLE. Of course, an account can be flipped for several times - If Alice is flipped again, it votes for LIKE again. And if we called the account the flipped account (Notice it's only a concept indicates the account has been flipped and not an attribute of an account), all accounts which forwarding the flipped account's microblog will also be flipped.

Soon, Edward found that someone uses this bug before! Some accounts have been flipped already. He can't spend XPower Point to flip them anymore; instead, he need spend YPower Point to flip an account which has been flipped directly by someone.

For the glory of the LIKE, please help Edward to flip accounts so that the Power Point of LIKE can be larger than CANDLE as much as possible.

You can spend Power Point as much as you like, no matter the total Power Point of LIKE is negative or not.

Input

The input contains no more than 20 test cases. Notice there's no empty line between each test case.

For each test case, first line has three integers N (1 ≤ N ≤ 50000) - the number of the accounts, X (0 ≤ X ≤ 1000) and Y (0 ≤ Y ≤ 1000) - as the problem description. The account is numbered from 1 to N and 0 represent the original account.

Following N lines, the i^th line means the i^th account. Each line has four integers: V (0 ≤ V ≤ 1000) - the value of the i^th account, F (0 ≤ F ≤ N) - which account did the i^th account's forwarding account come from (0^th microblog is original account's microblog), S (0 ≤ S ≤ 1) - the status of flipped (0 means no changed, 1 means changed) and P (0 ≤ P ≤ 1) - the side the account supports without flipped (0 means LIKE, 1 means CANDLE).

The original microblog's account can't be flipped, and it hasn't the value and the support side.

Output

For each test case print an integer, represents the maximum result of the value of LIKE minus the value of CANDLE. If the value of CANDLE is larger than the LIKE, then just output "HAHAHAOMG" (without quote).

Sample Input

Sample Output

题意：若干微博账户形成了一个转发树（即一个有根树）。每个账户有自己的价值，每个账户也有自己的态度（赞或蜡烛）。如果一个账户的态度是“赞”，它的价值就会被加到“赞”的一边，反之亦然。Edward可以从“赞”的一边拿出X 的价值去翻转一个账户，即把它的态度换到相反的一边。但是Edward 发现，有的账户已经被别人翻转过了，对于这些账户，Edward就要花费Y的价值去翻转它们。一旦一个账户被翻转了一次，它的所有子账户也会被翻转一次。求“赞”的一边的价值总数与“蜡烛”一边的价值总数的最大差值。若最大差值为负数则输出“HAHAHAOMG”。

输入：N个账户，X flip一个没有fliped的账户需要的花费，Y flip一个已经fliped的账户需要的花费。

四个数：账户价值，转发来源，是否要被flip（1表示要），被flip之前的状态（1表示蜡烛，0表示like）

思路：DP，dp[i][0/1]表示是第i个账户是否被flip之后的最大价值。

转移方程：dp[i][0] += max(dp[j][0],f[j][1] - (flip[j]?Y:X));

dp[i][1] += max(dp[j][1],f[j][0] - (flip[j]?Y:X));

代码如下：

//#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define maxn 50050
int dp[maxn][2];
int n,X,Y;
bool state;//表示当前的账户的zan或者蜡烛表示的价值是正还是负。
int v[maxn],f,s[maxn],p;
struct node{int t,nxt;
}edge[maxn<<1];
int head[maxn];
bool vis[maxn];
void solve(int u)
{vis[u] = 1;if(s[u])state ^= 1;if(state)v[u] = -v[u];dp[u][0] = v[u];dp[u][1] = -v[u];for (int i = head[u]; i!=-1; i = edge[i].nxt){int y = edge[i].t;if(!vis[y]){solve(y);dp[u][0] += max(dp[y][0],dp[y][1]-(s[y]?Y:X));dp[u][1] += max(dp[y][1],dp[y][0]-(s[y]?Y:X));}}if(s[u]) state ^= 1;
}
int main()
{while(scanf("%d%d%d",&n,&X,&Y)!=EOF){memset(dp,0,sizeof(dp));memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));int ind = 0;state = 0;for (int i = 1; i <= n; i++){scanf("%d%d%d%d",&v[i],&f,&s[i],&p);if(p) v[i] = -v[i];edge[ind].t = i;edge[ind].nxt = head[f];head[f] = ind++;}solve(0);if(dp[0][0] < 0)puts("HAHAHAOMG");else printf("%d\n",dp[0][0]);}return 0;
}

很抱歉，我这个程序在ZOJ上能过，在Hdu上就栈溢出RE了，应该是递归层数过深，可是手动扩栈了也不行，等什么时候过了再修改吧╮(╯▽╰)╭

这篇关于树形DP(2)-Hdu 4799 LIKE vs CANDLE的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！