思路概述

• 核心思想（树形 DP + 重心换根思想的双向合并）：

  • 对每个节点 $v$ 维护一个升序列表 down[v]，存 $v$ 到其子树内红点的最小 $K$ 个距离；
  • 再做一次“换根”传递，得到每个节点从父侧与其它兄弟子树来的最小 $K$ 个距离，记为 up[v]；
  • 对于每个节点 $v$，将 down 的所有子贡献、up[v]、以及自身是否为红点（贡献 $0$）合并，取最小 $K$ 个，其和即为 $F(v)$。

• 关键合并技巧：

  • 维护有序数组的“前 $K$ 小合并”函数，复杂度为 $O(K)$；

题目内容

给定一棵包含 $n$ 个节点的无向带权树，每条边 $(u, v)$ 的权重为正整数 $w_{uv}$。树上共有 $m$ 个标记为"红点"的节点。给定一个整数 $K (1 ≤ K ≤ m)$ ，对于每个节点 $v$ ，定义该节点到树中 $K$ 个最近红点的距离和：$F(v) = \sum_{i=1}^{K}$ $d_i(v)$ 其中 $d_1(v) ≤ d_2(v) ≤ … ≤ d_K(v)$ 是节点 $v$ 到所有红点按距离从小到大排序的前 $K$ 个距离。请计算所有节点的 $F(v)$ 。

输入描述

第一行输入三个整数 $n, m, K (2 ≤ m ≤ n ≤ 2 × 10^5, 1 ≤ K ≤ min(100, m))$ , 分别表示节点数、红点数和 $K$ 。

第二行输入 $m$ 个互不相同的整数 $r_1, r_2, …, r_m (1 ≤ r_i ≤ n)$ ，表示红点节点编号。

接下来 $n-1$ 行，每行输入三个整数 $u_i, v_i, w_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^6)$ ，表示一条无向带权边。

保证输入构成一棵树。

输出描述

输出一行，包含 $n$ 个整数 $F(1), F(2), …, F(n)$ ，用空格分隔。

样例1

输入

5 3 1
2 4 5
1 2 1
2 3 1
3 4 1
4 5 1

输出

1 0 1 0 0

样例2

输入

7 3 2
2 4 7
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1

输出

4 2 2 2 3 3 3