P3566.第4题-K-小距离
题目内容
给定一棵包含 n 个节点的无向带权树，每条边 (u,v) 的权重为正整数 wuv。树上共有 m 个标记为"红点"的节点。给定一个整数 K(1≤K≤m) ，对于每个节点 v ，定义该节点到树中 K 个最近红点的距离和：F(v)=∑i=1K di(v) 其中 d1(v)≤d2(v)≤…≤dK(v) 是节点 v 到所有红点按距离从小到大排序的前 K 个距离。请计算所有节点的 F(v) 。
输入描述
第一行输入三个整数 n,m,K(2≤m≤n≤2×105,1≤K≤min(100,m)) , 分别表示节点数、红点数和 K 。
第二行输入 m 个互不相同的整数 r1,r2,…,rm(1≤ri≤n) ，表示红点节点编号。
接下来 n−1 行，每行输入三个整数 ui,vi,wi(1≤ui,vi≤n,ui=vi,1≤wi≤106) ，表示一条无向带权边。
保证输入构成一棵树。
输出描述
输出一行，包含 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
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
