【NOIP模拟赛】Kth

2014年10月30日1,2150

【题目描述】

给定一个N(2<=N<=150000)个节点N-1边的树,每条边有一个长度L(1<=L<=1000000)。

现在定义:

  • “路径(u,v)长度”表示顶点u到v之间的最短路径
  • “u的第k远路径”表示从顶点u出发的第k长路径。

请编写一个程序,计算这棵树中每个顶点的的第k远路径的长度。

【输入格式】

输入第一行包含一个整数T(T<=50),表示测试数据的组数。

在每一组测试数据中,第一行为两个整数N和K(1<=K<=20且K<=N-1)。接下来的N-1行,每行包含三个整数u,v,L(0<=u,v<=N-1),表示顶点u到v有一条边长度为L。

【输出格式】

对于每组数据,输出一行,为N个整数(之间用一个空格隔开),其中第i(i=0,1,2,…,N-1)个整数表示顶点i的答案。

【样例输入】

2

4 1

0 1 4

1 2 5

2 3 9

3 2

0 1 12

0 2 19

【样例输出】

18 14 9 18

12 12 19

题解

树形dp。。。f[x]和g[x]分别表示从x出发,终点在/不在x的子树中的1-K远距离

转移的时候通过归并每次为K,还要搞类似前缀和后缀和的好麻烦。。

复杂度为TNK。。。