Sorted Paths

頂点からなる木があり、 番目の辺は頂点 と頂点 を結んでいます。また頂点 には整数 が書かれています。
ここで 頂点 から頂点 への最短パス上の頂点に書かれた数の最大値 と定義します。
頂点から異なる頂点対 を選ぶ方法すべてに対する を求めてそれらを昇順に並べた時、前から 番目となる要素を求めてください。

• 入力はすべて整数
• 与えられるグラフは木

答えを出力し、最後に改行してください。

3 2
1 2
2 3
6 5 4

6

であるのでこれらを昇順に並べた の 番目の要素 が答えとなります。

5 1
2 4
2 3
1 4
4 5
4 1 3 1 7

1

9 18
1 5
5 6
4 5
6 9
2 6
5 8
1 3
7 8
19 3 5 17 18 12 6 11 1

18