题意:一棵有根树,每个节点都有一个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 ;
}

最新文章

  1. WinMain初始化详细过程以及消息循环
  2. Delphi GDI+基本用法总结
  3. 定制属于自己的自动化安装的linux系统镜像
  4. TCP/IP协议原理与应用笔记07:HTTP、TCP/IP与socket区别
  5. 类 的继承性(Inherits)与 重写(Overrides)
  6. div的替代品
  7. docker疑难解答 -- 设置远程服务监听
  8. threejs - uv 映射 简要
  9. 常见jquery面试题
  10. Working with PDF files in C# using PdfBox and IKVM
  11. post 数据
  12. [BZOJ 2705] [SDOI 2012] Longge的问题
  13. 【nodejs】初识 NodeJS(四)
  14. springboot配置文件启动顺序
  15. ajax的基础
  16. 利用hadoop来解决“单表关联”的问题
  17. python标准库介绍——30 code 模块详解
  18. Java8系列之重新认识HashMap(转)
  19. 【洛谷】【扩欧】P1516 青蛙的约会
  20. WCF系列教程之WCF中的会话

热门文章

  1. node.js里的forEach()也是异步的吗?
  2. 【2】认识Bootstrap
  3. RSA算法解析
  4. C语言小知识
  5. 角色控制器 Character Controller
  6. ionic+angulajs
  7. python 常用模块(转载)
  8. maven编译的时候排除junit测试类
  9. nutch 生产者队列的大小如何控制 threadcount * 50
  10. 《暗黑世界GM管理后台系统》部署+功能说明