分数: 433 分
问题陈述
一个城镇有 N 由以下连接的交叉路口 N - 1 道路。任何两个交叉路口都可以通过沿着一条唯一路径(即交叉路口和道路形成树结构)的道路相互到达。
的 距离 交叉路口之间 a 和交叉路口 b 定义为从 a to b。特别是距交叉路口的距离 a 本身就是 0.
最初,任何十字路口都没有商店。在一段时间内 Q 天,当天 i (1 \leq i \leq Q),十字路口新开了一家商店 C_i。任何十字路口的商店都不会营业多次。商店一旦开业,就会无限期地继续经营。
当青木站在镇上的某个路口时,如果恰好有 1 距离内的商店 R 或更少,因为他可以完全拥有那家商店。
对于每一天,确定当天结束时青木会感到快乐的交叉点数量。即求交点的个数 x 使得距离内的商店数量 R 从交叉路口 x 正是 1。请注意,如果相交 x 本身有一个商店(距离 0),也算在店铺之中。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq N
- N + Q \leq 2 \times 10^5
- 1 \leq R \leq 20
- 1 \leq u_i, v_i \leq N
- u_i \neq v_i
- 给定的图是一棵树
- 1 \leq C_i \leq N
- 全部 C_i 是不同的
- 所有输入值均为整数
输入
N Q R
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
C_1
C_2
\vdots
C_Q
- 第一行包含交叉点的数量 N,天数 Q,以及距离限制 R,用空格分隔。
- 以下 N - 1 行每行包含 u_i 和 v_i 用空格隔开,表示有道路连接路口 u_i 和交叉路口 v_i.
- 后续 Q 行每行包含 C_i, 当天新开店的路口号 i.
输出
A_1 A_2 \vdots A_Q
关于 i第行,输出 A_i,距离内商店数量的路口数量 R 正是 1,在一天结束时 i.
示例输入 1
5 3 1 1 2 2 3 3 4 4 5 3 1 5
示例输出 1
3 3 3
示例输入 2
6 4 2 1 2 1 3 1 4 1 5 1 6 2 3 4 5
示例输出 2
6 0 0 0
示例输入 3
15 8 2 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 6 11 6 12 7 13 13 14 13 15 8 12 5 14 1 10 7 3
示例输出 3
4 8 9 13 8 7 4 2
示例输入 4
40 20 4 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 5 11 5 12 6 13 7 14 7 15 8 16 9 17 10 18 10 19 11 20 12 21 13 22 14 23 15 24 16 25 17 26 18 27 19 28 20 29 21 30 22 31 23 32 24 33 25 34 26 35 27 36 28 37 29 38 30 39 31 40 38 34 22 5 27 15 40 1 19 30 8 36 24 12 3 33 10 29 6 17
示例输出 4
5 10 16 13 15 19 17 8 7 5 4 4 3 3 2 2 0 0 0 1
示例输入 5
1 1 20 1
示例输出 5
1