2015
09-18

# HDU 4799-LIKE vs CANDLE-动态规划-[解题报告]HOJ

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 ith line means the ith account. Each line has four integers: V (0
V ≤ 1000) – the value of the ith account, F (0 ≤ F  N) – which account
did the ith account’s forwarding account come from (0th 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

4 3 2
5 0 0 0
3 1 0 1
4 2 1 0
1 2 0 0

Sample Output

8

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

#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];
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(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;
}
solve(0);
if(dp[0][0] < 0)
puts("HAHAHAOMG");
else printf("%d\n",dp[0][0]);
}
return 0;
}

1. 我们民族经历了那么那么多，有的是外来的，但大多数是内忧，我觉得我们的内忧是多于外患的，大多数是自找的。——透彻！

2. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

3. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

4. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

5. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

6. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

7. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

8. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

9. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

10. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

11. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

12. 我是个路人，但我想说几句，首先别老催三哥，他很忙，要写书还要画漫画又要拍电视电影找人物，休息时间都没有，三哥你要是看见的话，我不希望你更快我只希望你健康不要每天一更一周一次也好，不要忙出病，不舒服就别忙了休息吧我们不怪你，写书不要急，不要写错了，我们斗罗

13. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

14. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

15. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

16. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

17. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

18. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

19. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

20. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

21. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

22. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

23. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

24. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

25. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

26. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

27. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

28. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥

29. 因噎废食当然也不好，但总得有人提出质疑和异见。在大部分时候，我们却很容易因为一通话一顿饭一篇文章就人云亦云，盖棺定论，我只是觉得这样不好，至于说信什么不信什么，“实践是检验真理的唯一标准啊”老哥