これはインタラクティブな問題である。

この問題は高速な言語で解答することを推奨する。C++14 (GCC 5.4.1) で AC できることが確認されている。

問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

今日は夏休み。きたむーは愛する彼女と虫取りに来ている。実は虫取りは二人の愛を深める非常に有意義な共同作業なのだ！

きたむーは$1$本のりんごの木を見つけた。このりんごの木は $1$ 個の根、$N-1$ 個の葉または節点、 $N-1$ 本の枝からなり、情報科学で言うところの木構造と酷似している。葉または節点、および根のことを以下では頂点と呼ぶ。根には番号 $0$ が、各頂点には番号 $1 \\sim N-1$ が振られている。はじめ、きたむーは根にいる。

このりんごの木からは美味しい果実が取れるので、頂点にはすぬけ虫がやってくる。すぬけ虫は群れで生活していて非常に賢く、ある頂点を根とした部分木の各頂点に分散して止まる。例えば頂点数 $3$ の部分木に $15$ 匹のすぬけ虫がやってきたとき、 $5$ 匹ずつに分かれて各頂点に止まる。なお、すぬけ虫は群れの虫の数が頂点数で割り切れないような部分木にはやってこない。なお、最初各頂点に止まっているすぬけ虫は $0$ 匹である。

この木は非常に高くそびえており、虫取り網ではとても届かないので、きたむーは頂点間を移動してすぬけ虫を取ることにした。ただし、いちいち木を降りてすぬけ虫の居場所を確認していては時間が勿体ないので、彼女から $Q$ 回指示を受けて、頂点間を移動することにした。

指示は以下の $2$ 種類からなる。

指示 $A$ は

$0$ $i$ $k$

という形で与えられる。これは、$i$ 番目の頂点を根とする部分木に $k$ 匹のすぬけ虫の群れがやってきたことを意味する。

指示 $B$ は

$1$ $i$

という形で与えられる。このとき、きたむーは現在いる頂点から $i$ 番目の頂点まで、最短経路で移動する。その際、始点・終点を含む移動中に通った頂点にいたすぬけ虫をすべて捕獲し、その総数を彼女に報告する。その後、きたむーは次の指示 $B$ があるまで頂点 $i$ にとどまる。

二人の愛を試す虫取りの試練が今始まる・・・。

制約

• 入力はすべて整数
• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq Q \\leq 8 \\times 10^4$
• $0 \\leq C_j,D_j \\leq N-1\\ (1 \\leq j \\leq N-1)$
• 入力されるグラフは木である
• $0 \\leq i \\leq N-1$
• $0 \\leq k \\leq 10^{9}$
• $k$ は頂点 $i$ を根とする部分木の頂点数で割り切れる

部分点

• 以下の入出力例に正解すると $1$ 点が得られる。
• すべてのテストケースに正解すると、さらに $1199$ 点が得られる。

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$ $C_1$ $D_1$ $C_2$ $D_2$ $\\vdots$ $C_{N-1}$ $D_{N-1}$ $指示1$ $指示2$ $\\vdots$ $指示Q$

ここで、整数 $C_i,\\ D_i$ は、 $N-1$ 本の枝のうち $i$ 番目の枝は頂点 $C_i$ と $D_i$ を結んでいるという意味である。

出力

指示 $B$ が与えられるごとに、捕まえたすぬけ虫の総数を報告せよ。

実装上の注意

• この問題は インタラクティブな問題 である。指示 $B$ が与えられた後に捕まえたすぬけ虫の数を報告しない限り、次の指示が与えられないので注意せよ。
• 出力のあと、標準出力を flush しなければならない。 そうでないときは TLE の可能性がある。
• 答えを出力した後、プログラムをすぐに終了しなければならない。そうでないときの挙動は定義されていない。
• 出力の答えが間違っている場合の挙動は定義されていない ( WA とは限らない)。

---

入力例 1

6 4
0 3
3 1
3 2
4 5
0 5
0 3 9
0 1 2
0 2 5
1 1

出力例 1

8

---

入力例 2

9 9
0 5
0 2
0 1
5 8
5 7
5 4
2 3
2 6
0 0 9
0 2 6
0 8 4
1 8
1 1
0 3 8
0 0 144
0 3 32
1 3

出力例 2

7
1
110

実際には指示 $B$ のあとに解答を出力しないと次の指示が与えられないことに注意せよ。

---

解説

解説