F - Labeled Tree Distance Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 頂点の木 T が与えられます。辺 i は頂点 u_i と v_i を結んでいます。 最初、頂点 i は色 A_i で塗られています。 Q 個のクエリが与えられるので、順番に処理してください。クエリは次の 2 種類のいずれかです。

  • 1 k x: 頂点 k を色 x で塗る
  • 2 y: 色 y で塗られている 2 頂点の距離の最大値を出力する

ここで、2 頂点 (u,v) の距離とは、u と v を両端点とするパスに含まれる辺の本数です。

制約

  • 2 \le N \le 10^5
  • 1 \le u_i,v_i \le N
  • 1 \le A_i \le N
  • 1 \le Q \le 10^5
  • 1 \le k \le N
  • 1 \le x \le N
  • 1 \le y \le N
  • クエリ2 yが与えられるとき、色 y で塗られている頂点が 2 つ以上存在する
  • 入力は全て整数である
  • 与えられるグラフは木である

入力

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

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
A_1\  A_2\  \ldots\  A_N
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

ここで、\mathrm{query}_i は i 個目のクエリであり、以下のいずれかの形式で与えられます。

1 k x

2 y

出力

2番目の形式のクエリの回数を q として q 行出力してください。 j (1\leq j \leq q) 行目では 2 番目の形式のクエリのうち j 個目のものに対する答えを出力してください。

入力例 1

3
1 2
2 3
1 1 1
3
2 1
1 1 2
2 1

出力例 1

2
1

最初、全てのマスが色 1 で塗られています。このとき、色 1 で塗られている 2 頂点のうち、頂点 1 と頂点 3 の距離が最大となり、その距離は 2 です。 その後、頂点 1 が色 2 で塗られると、色 1 で塗られている頂点では頂点 2 と頂点 3 の距離である 1 が最大となります。

入力例 2

4
1 2
1 3
1 4
1 1 2 2
5
2 1
2 2
1 1 3
1 3 3
2 3

出力例 2

1
2
1

入力例 3

6
1 2
2 3
3 4
4 5
4 6
1 3 2 1 1 3
6
2 1
1 2 3
1 1 2
1 6 4
2 1
2 2

出力例 3

4
1
2