Problem G: NO Intersections Plz
Problem G: NO Intersections PlzTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 190 Solved: 47
Given a weighted tree with \(N\) nodes. The distance of a simple path is defined as the sum of all edges in the path. You should choose \(M\) simple paths with no edge intersection between any two paths (But two paths can intersect at certain nodes). Now you are asked to calculate the maximum distance of the shortest path.
The first line contains two integers \(N\) and \(M(1\leq M< N\leq 5\times 10^4)\)
The next \(n-1\) lines each contain three integers \(x,y,w\), denoting there is an edge with weight \(w\) connecting \(x\) and \(y(1\leq x,y\leq N,1\leq w\leq 10^4)\)
Output one single integer, indicating the maximum distance of the shortest path.
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7