頂点の木があり、頂点はと番号付けられています。
番目の辺は頂点と頂点を結び、重みはです。
異なる頂点に対し、頂点から頂点までのパスに含まれる辺の重みの総和をとおきます。
を満たす全てのに対するを並べた数列を考えます。
この数列を昇順に並び替えた時、先頭から番目の要素を求めてください。
入力は以下の形式で標準入力から与えられる。
答えを出力せよ。
4 5 1 2 1 2 3 2 2 4 3
4
となります。
これらを昇順に並び替えた時、となるので、先頭から番目のを出力します。
12 15 7 8 200461365 1 4 142541250 10 12 932937719 2 6 913604024 6 8 942889106 3 6 997126869 8 11 861400492 8 9 329257068 1 8 64078190 5 7 214221265 9 10 927859136
743939698