#P17710. [2026年江苏省队集训]树上游戏

[2026年江苏省队集训]树上游戏

题目描述

小 H 和小 Q 在一棵 nn 个点的无根树上玩游戏,边有边权,两点间的距离定义为树上唯一路径的边权和。

小 H 已经在树上选择了若干节点作为她的关键点,小 Q 需要在没有被小 H 选中的点中选择至多 mm 个节点作为他的关键点。

选完关键点后,树上每个节点会被距离它最近的关键点覆盖,如果有多个距离相同的最近点,则会被其中在树上标号最小的覆盖。求小 Q 最多能覆盖多少树上的节点。

对每个 m∈[1,n]m\in [1,n],回答上述问题的答案。

输入格式

第一行一个正整数 nn。

接下来 n−1n-1 行,每行三个正整数 u,v,wu,v,w,表示 u,vu,v 之间有一条权值为 ww 的边。

最后一行一个长度为 nn 的数组 p (pi∈{0,1})p~(p_i\in\{0,1\}),pi=1p_i=1 表示 ii 被小 H 选为了关键点,pi=0p_i=0 则没有。

输出格式

一行 nn 个正整数,依次表示每个 mm 的答案。

样例

样例 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 解释

.png

  • 当 m=1m=1 时,选择 22 号节点可以覆盖 2,32,3 两个节点。
  • 当 m≥2m\ge 2 时,选择 2,42,4 号节点可以覆盖 2,3,42,3,4 三个节点。

可以证明不存在更优的覆盖。

样例 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

数据范围与约定

对于全部数据,1≤n≤5000,1≤w≤1051\le n\le 5000,1\le w\le 10^5,保证初始至少存在一个节点被小 H 覆盖。

Subtask 分值 n≤n\le
1 5 1010
2 25 5050
3 30 500500
4 40 50005000