AT_kupc2021_l Tag Game

[problemUrl]: https://atcoder.jp/contests/kupc2021/tasks/kupc2021_l $ N $ 頂点の木があります。この木の辺の長さはすべて $ 1 $ です。この木の上で $ Q $ 回鬼ごっこをします。あなたは逃げる側であり、鬼ごっこの開始時に鬼はあなたと異なる頂点にいます。鬼はあなたのいる場所を常に知っていて、毎秒 $ 1 $ の速さであなたを追いかけます。あなたは鬼の位置はわかりませんが、鬼までの距離は鬼の匂いの濃度から常にわかります。その情報をもとに、毎秒以下の $ 2 $ つの動作のうち $ 1 $ つを行います。 - $ 1 $ 秒かけて隣接する頂点に進む - $ 1 $ 秒間今いる頂点で静止する 辺上か頂点上で鬼と会ったら、その回の鬼ごっこは終了です。 $ i $ 回目の鬼ごっこの開始時では、あなたは頂点 $ x_i $ にいて、鬼までの距離が $ d_i $ であることがわかっています。鬼と出会うまでの時間の最小値を最大化するように行動したときの、鬼に会うまでの時間の最小値 $ s_i $ を求めてください。 (つまり、答えはあなたは得られた情報から賭けをすることなく鬼と出会わないように動くときの鬼と出会うまでの時間の最小値です。また、辺上での移動は等速運動とし、鬼はあなたとの距離を縮める方向に動きます。)

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_{N-1} $ $ b_{N-1} $ $ x_1 $ $ d_1 $ $ x_2 $ $ d_2 $ $ \vdots $ $ x_Q $ $ d_Q $ $ 1 $ 行目には頂点数 $ N $ と鬼ごっこの回数 $ Q $ が入力される。$ 2 $ 行目から $ N $ 行目で木の情報が与えられる。$ i+1 $ 行目には頂点 $ a_i,b_i $ が辺で結ばれていることを示している。 $ N+1 $ 行目から $ N+Q $ 行目には $ Q $ 回の鬼ごっこの情報が与えられる。$ N+i $ 行目には $ i $ 回目の鬼ごっこ開始時にあなたがいる頂点 $ x_i $ と、そのときの鬼までの距離 $ d_i $ が与えられる。

> $ s_1 $ $ s_2 $ $ \vdots $ $ s_Q $ $ i $ 行目に $ i $ 回目の鬼ごっこで鬼と出会うまでの時間の最小値を最大化するように行動したときの、鬼に会うまでの時間の最小値 $ s_i $ を出力せよ。$ s_i $ は必ず整数となることが示せる。

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 1\ \leq\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ a_i,b_i\ \leq\ N $ - $ 1\ \leq\ x_i,d_i\ \leq\ N $ - 頂点 $ x_i $ から距離が $ d_i $ である頂点は必ず存在する。 - $ i\ \neq\ j $ のとき $ (x_i,\ d_i)\ \neq\ (x_j,\ d_j) $ - 与えられるグラフは必ず木である。 - 入力は全て整数である。 ### Sample Explanation 1 $ 1 $ 回目の鬼ごっこの開始時には、あなたは頂点 $ 1 $ にいて、鬼までの距離は $ 4 $、つまり鬼は頂点 $ 5 $ にいます。このときは、頂点 $ 1 $ にずっととどまる行動が最適となり、$ s_1\ =\ 4 $ となります。 $ 2 $ 回目の鬼ごっこの開始時には、あなたは頂点 $ 3 $ にいて、鬼までの距離は $ 1 $、つまり鬼は頂点 $ 2 $ か頂点 $ 4 $ のどちらかにいます。この後あなたが頂点 $ 2 $ の方向に動いたとすると、鬼がはじめ頂点 $ 2 $ にいたときは、$ 0.5 $ 秒後に辺上で出会い、頂点 $ 4 $ にいたときは、$ 3 $ 秒後に頂点 $ 1 $ で出会います。よって、この行動をしたときの鬼と出会うまでの最小値は $ 0.5 $ となります。 頂点 $ 4 $ の方向に動いたときも同様に鬼と出会うまでの最小値は $ 0.5 $ となります。 もし、あなたが動かず頂点 $ 3 $ にとどまっていたとすると、鬼が頂点 $ 2 $ にいたとき $ 1 $ 秒後に、頂点 $ 4 $ にいたときも $ 1 $ 秒後に出会います。よって、この行動をしたときの鬼と出会うまでの最小値は $ 1 $ となります。 したがって、あなたの最適な行動は頂点 $ 3 $ にとどまることで、その時の鬼に会うまでの時間の最小値 $ s_2 $ は $ 1 $ となります。