[2010国家集训队]Crash的旅游计划

时间限制:150s      空间限制:552MB

题目描述

眼看着假期就要到了,Crash由于长期切题而感到无聊了,因此他决定利用这个假期和好友陶陶一起出去旅游。 Crash和陶陶所要去的城市里有N (N > 1) 个景点,Crash用正整数1到N给景点标号。这些景点之间通过N − 1条无向道路相连,每条道路有一个长度,并且保证任意两个景点之间都有且仅有一条路径相连。现在对于一个景点s,Crash和陶陶从s出发,然后访问一个景点序列{v0, v1, v2, … , vk},其中v0就是s,且vi-1和vi(0 < i ≤ k)之间有道路相连。需要注意的是,陶陶和Crash访问的景点序列中不会只有景点s。为了使旅程不显得乏味,在一个景点序列里他们不会重复走某条道路。我们定义这个序列的旅游代价为经过道路的长度和。下面问题出现了:陶陶:我们走一条景点数最多的景点序列吧。 Crash:倒,你想把我累死啊。陶陶:谁叫你整天坐在电脑前面,不出来锻炼,这下子傻了吧,哈哈哈哈~~ Crash:不行,如果你非要走景点数最多的我就不陪你走了。陶陶:笑喷油你很跳嘛! Crash:这样吧,我们来写伸展树,如果我写的比你快,你就要听我的。陶陶:这样不公平哎,我们来玩PES吧,当然你要让我选法国队,如果你输了你就要听我的。 Crash:倒,你这是欺负我,T_T~ 陶陶:笑喷油好说话哎。 Crash:囧…… …… 这样搞了半天,最终陶陶和Crash用很多次包剪锤决定出选择旅游代价第K小 的景点序列。不过呢Crash和陶陶还没确定开始旅行的景点s,因此他希望你对于每个景点i,计算从景点i开始的景点序列中旅游代价第K小的值。


输入格式

共N行。第1行包含一个字符和两个正整数,字符为ABCD中的一个,用来表示这个测试数据的类型(详见下面的数据规模和约定),另外两个正整数分别表示N和K (K < N)。第2行至第N行,每行有三个正整数u、v和w (u, v ≤ N,w ≤ 10000)。表示u号景点和v号景点之间有一条道路,长度为w。输入文件保证符合题目的约定,即任意两个景点之间都有且仅有一条路径相连。


输出格式

共N行,每行有一个正整数。第i行的正整数表示从i号景点开始的景点序列中旅游代价第K小的代价。


样例输入

A 6 3
1 2 2
1 3 4
1 4 3
3 5 1
3 6 2

样例输出

4
6
4
7
5
6

提示

样例1中输出对应的景点序列分别为:1号景点是{1, 3},2号景点是{2, 1, 3},3号景点是{3, 1},4号景点是{4, 1, 3},5号景点是{5, 3, 1},6号景点是{6, 3, 1}。 保证每个景点到1号景点需要经过的道路数不超过30。 N ≤100000


题目来源

没有写明来源