問題文
N 頂点からなる木があり、i (1≤i≤N−1) 番目の辺は頂点 Ai と頂点 Bi を結んでいます。また頂点 j (1≤j≤N) には整数 Cj が書かれています。
ここで f(u,v)=(頂点 u から頂点 v への最短パス上の頂点に書かれた数の最大値) と定義します。
N 頂点から異なる頂点対 u<v を選ぶ方法すべてに対する f(u,v) を求めてそれらを昇順に並べた時、前から K 番目となる要素を求めてください。
制約
- 入力はすべて整数
- 2≤N≤2×105
- 1≤K≤2N(N−1)
- 1≤Ai<Bi≤N
- 与えられるグラフは木
- 1≤Cj≤109
入力
出力
答えを出力し、最後に改行してください。
入力例1
出力例1
f(1,2)=6,f(1,3)=6,f(2,3)=5 であるのでこれらを昇順に並べた (5,6,6) の 2 番目の要素 6 が答えとなります。
入力例2
5 1
2 4
2 3
1 4
4 5
4 1 3 1 7
出力例2
入力例3
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
出力例3