#P17710. [2026年江苏省队集训]树上游戏
[2026年江苏省队集训]树上游戏
题目描述
小 H 和小 Q 在一棵 个点的无根树上玩游戏,边有边权,两点间的距离定义为树上唯一路径的边权和。
小 H 已经在树上选择了若干节点作为她的关键点,小 Q 需要在没有被小 H 选中的点中选择至多 个节点作为他的关键点。
选完关键点后,树上每个节点会被距离它最近的关键点覆盖,如果有多个距离相同的最近点,则会被其中在树上标号最小的覆盖。求小 Q 最多能覆盖多少树上的节点。
对每个 ,回答上述问题的答案。
输入格式
第一行一个正整数 。
接下来 行,每行三个正整数 ,表示 之间有一条权值为 的边。
最后一行一个长度为 的数组 , 表示 被小 H 选为了关键点, 则没有。
输出格式
一行 个正整数,依次表示每个 的答案。
样例
样例 1 输入
5
2 1 3
3 2 4
4 3 9
5 4 1
1 0 0 0 1
样例 1 输出
2 3 3 3 3
样例 1 解释

- 当 时,选择 号节点可以覆盖 两个节点。
- 当 时,选择 号节点可以覆盖 三个节点。
可以证明不存在更优的覆盖。
样例 2 输入
10
2 1 2
3 2 6
4 2 10
5 1 9
6 3 2
7 2 7
8 4 3
9 7 3
10 1 2
0 0 0 0 1 0 1 1 0 0
样例 2 输出
5 6 7 7 7 7 7 7 7 7
数据范围与约定
对于全部数据,,保证初始至少存在一个节点被小 H 覆盖。
| Subtask | 分值 | |
|---|---|---|
| 1 | 5 | |
| 2 | 25 | |
| 3 | 30 | |
| 4 | 40 |