No.2258 The Jikka Tree
問題文
まず、 頂点の木が与えられます。頂点には から まで番号が付けられています。 辺は 個ありますが、 番目の辺( )は頂点 と頂点 を結びます。 与えられた木の 頂点 , に対して、 , 間の最短パスに含まれる辺の個数を と表します。 のときは です。 さらに、数列 が与えられます。
を満たす整数 , と頂点 、頂点 、非負整数 に関して と定義します。
ここで、 個のクエリが与えられます。 番目のクエリ では与えられる非負整数 , , , に対して、 の値を最小化するような の番号を求めてください。そのような はこの問題の制約のもとで一意です。 番目のクエリの答えを とします。
実際には、 番目のクエリでは , , の代わりに , , が与えられるので、それ以前のクエリの答えを用いて次の手順で復元してください。
- のときは 、 のときは とする。
- のときは 、 のときは とする。
- のときは 、 のときは とする。
ちなみに、 は素数です。
制約
入力は次の制約を満たします。
- 与えられた辺からなるグラフは木である
- 入力はすべて整数
また、復元された , , は次の制約を満たすことが保証されます。
入力
入力は次の形式で与えられます。
出力
サンプル
サンプル1
入力
5 0 1 1 3 3 2 3 4 1000 10 1 100 10000 15 0 0 0 0 0 1 150000 1 2 0 0 2 3 0 150000 3 4 2 150000 4 1 1 149975 0 0 0 149965 1 1 2 149951 2 1 4 149901 3 3 4 149804 4 2 0 149745 0 3 1 149639 1 1 4 149517 2 4 3 149375 3 0 1 149160 4
出力
0 0 0 1 4 1 1 3 4 2 3 3 3 4 4
クエリの内容を復元した , , で置き換えた入力データを次に示します。
5 0 1 1 3 3 2 3 4 1000 10 1 100 10000 15 0 1 0 0 0 2 150000 1 0 3 0 2 0 4 150000 3 0 5 0 4 1 2 150000 0 1 3 0 1 1 4 150000 2 1 5 0 3 2 3 150000 4 2 4 0 0 2 5 150000 1 3 4 0 2 3 5 150000 3 4 5 0 4
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。