Problem D: 两颗葡萄
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$3$ |
正确数量 |
$2$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
图论 网络流 二分图 |
当前分类(单击移除)：
图论网络流二分图
单击选择分类：
小明家的老藤葡萄树可以看成是一个有根无向树，根节点编号为1。每个节点都有若干个葡萄。采摘葡萄时，每次选取两个相邻的节点，当这两个节点上都有葡萄时，则同时采摘下来（每个节点取一个葡萄）。直到树上不存在相邻两个节点都有葡萄的情况出现，采摘停止。老藤葡萄树相比普通葡萄树是有特殊的地方的：在某些节点会长出“先天葡萄”。“先天葡萄”具有益气补血的功效，非常珍贵，因此必须被采摘。注意：对于一个节点来说，要么只含有普通的葡萄，要么只含有“先天葡萄”，不会出现杂糅的情况。现在小明想请教你，在遵循上述规则的前提下，小明一家最多能采摘多少颗葡萄呢？如果无法完成目标，输出-1。少颗葡萄呢？如果
无法完成目标，输出-1
第一行输入正整数T，表示数据的组数。对于每组数据：第1行一个正整数n(n<=100000)，表示树的结点个数，1号为根结点。接下来n行每行3个整数，依次分别为
f1,c1,g1,f2,c2,g2,. . .,fn,cn,gn。表示编号为i的节点的父亲节点编号(0<fi<i)；表示编号为i的节点下面有多少颗葡萄(0<= ci <=10000)；gi表示编号为i的节点是否为先天葡萄，1表示是，0表示不是。注意：f1≡0，表示根节点没有父亲结点。
对于每组数据，输出一行，格式为'Case #t: x'，t为数据的组号，x为题目要求的结果。
1
4
0 2 0
1 3 0
1 1 1
3 5 0