SPOJ.com - Problem XYYHHTT

XYYHHTT - Catch Sheep

no tags

XiYangYang is a kind of lovely and rare sheep. They live in a peaceful land which can be described as a tree with N cities (nodes).

Now you have K robots. They will start at a same point and travel each edge at least once so that all XiYangYang will be caught. All your robots can stop at any city in the land. Because of expensive oil, you want minimize the total distance that your robots walk.

Input

First line : N K (N <= 15000, K <= 30)

Next N-1 lines: a b c (city a and city b are connected with a road whose length is c (1 <= a, b <= N, 0 <= c <= 100)

Output

N lines: The total distance that your robots walk if they all start at city i.

Example

Input:
5 3
1 2 7
2 3 5
3 4 14
3 5 8

Output:
42
39
34
42
42

Hint: my solution can get AC in 0.75~1 second.

Submit solution!

hide comments



	rafael859: 2015-03-16 18:27:50 I believe my solution has a complexity of O(NK), but I still get a TLE! I also made randomized big testcases and they run in under 0.25 seconds on my computer. And that's without the -O2 flag (with it, it runs in under 0.1 seconds). I do see that the time limit in the description is under that but it's outrageously low! Do I have to do pruning/optimizations? Has the time limit been automatically reduced since migrating to the new servers? Edit: Got AC after a little optimization Last edit: 2015-03-18 15:46:12*
	Ahmed Sherif: 2010-07-13 11:47:38 @Lewin Gan , thanks a lot dude :)
	Lewin Gan: 2010-07-13 11:47:38 case 1: Two robots stay in city one. One robot goes out and travels (1->2->3->5->3->4) for a total of (7+5+8+8+14) = 42 case 2: One robot travels (2->1) for a cost of 7. The second robot travels (2->3->5) for a cost of (5+8) = 13 and the last robot travels (2->3->4) for a cost of (5+14) = 19. The total cost is (7+13+19) = 39. case 3: One robot travels (3->5) for a cost of 8. The second robot travels (3->4) for a cost of 14. The third robot travels (3->2->1) for a cost of (7+5) = 12. The total cost is (8+14+12) = 34. case 4: Two robots stay in city 4. The other robot travels (4->3->5->3->2->1) for a cost of (14+8+8+5+7) = 42. case 5: One robot stays in city 5. One robot travels (5->3->4) for a cost of (8+14) = 22. The other robot travels (5->3->2->1) for a cost of (8+5+7) = 20. The total cost is (22+20) = 42.
	Ahmed Sherif: 2010-07-13 11:47:38 yeah , can someone kindly explain the output !?
	Kawmia Institutes: 2010-07-13 11:47:38 can anyone explain how the test cases be with that output
	Mahesh Chandra Sharma: 2010-07-13 11:47:38 Every robot have to traverse every edge or at least one robot have to traverse each edge? RE:at least one Last edit: 2010-07-07 11:35:23

Submit solution!

Added by:	刘启鹏
Date:	2010-07-07
Time limit:	0.100s-1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:	LvWeiCong(吕伟聪) at China NOI WinterCamp 2010