Problem H: 两颗葡萄

"
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
Case 1: 6