128MB,1S,mental.xxx
心灵支配树
问题描述
心灵军团建造了一棵心灵支配树,由 N 个节点(编号 1 到 N)构成,1 号点
为根节点,每个节点可以控制着战场某一个位置的敌军士兵(战场是一棵与心灵
支配树结构(含编号)相同的树),同时每个节点会控制其子树中的所有节点控
制的敌军士兵,由于启动支配树是要花钱的,所以异教会根据情况来决定使用哪
个节点。在启动支配树的某个节点后,异教想要把这些被控制的单位集中到一个
节点上,然而路上会遇到未被控制的敌军,只有消灭他们才能通过,为了评估这
种控制方案,异教想知道将这些被控制的敌军集中起来,路上需要消灭的敌军战
斗力之和的最小值。
现在已知心灵支配树,同时也是战场的结构,以及每个节点所控制的敌军数
量及其所在的节点编号,以及当前节点的敌军战斗力。请对于每个心灵支配树上
的节点输出将这个节点子树中所有节点控制的敌军集中到某个节点,路上需要消
灭的敌军战斗力之和的最小值。
选手可以自行开启 O2 测试
输入描述
第一行一个整数 N
接下来 N 行,每行若干个个整数 vi,ei,vi 表示战场上位于 i 号点的敌军的
战斗力,ei 表示支配树上 i 号点控制的敌军所在的节点编号。
接下来 N - 1 行,每行两个整数 u, v 表示 u 号点与 v 号点之间有一条边。
输出描述
N 行,每行一个整数,第 i 行的整数表示将 i 号点点子树中所有节点控制的敌
军集中到某个节点,路上需要消灭的敌军战斗力之和的最小值。
样例输入
7
评论0