Submit: 190 Solved: 47

[Submit][Status][Web Board]

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)\)

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.

```
7 1
1 2 10
1 3 5
2 4 9
2 5 8
3 6 6
3 7 7
```

`31`

**不要使用任何与堆和BST相关的STL！**