#include #include #include using namespace std; // 入力 int N, A[1 << 18], B[1 << 18]; int K, C[1 << 18]; int Q, T[1 << 18], X[1 << 18], Y[1 << 18]; // グラフ vector G[1 << 18], H[1 << 18]; bool used[1 << 18]; int cl[1 << 18], cr[1 << 18], dist[1 << 18], cnts; // データ構造 int sz[1 << 18]; int dat[1 << 18][22]; // 出力 long long Answer[1 << 18]; void init() { for (int i = 0; i < 18; i++) { for (int j = (1 << i); j < (2 << i); j++) sz[j] = i; } for (int i = 0; i < 21; i++) { for (int j = 0; j <= 2 * N; j++) { int t = j + (1 << i); dat[j][i + 1] = dat[j][i]; if (t <= 2 * N) dat[j][i + 1] = min(dat[j][i + 1], dat[t][i]); } } } int query(int cl, int cr) { // [cl, cr) if (cl >= cr) return (1 << 30); int f = sz[cr - cl]; int v1 = dat[cl][f]; int v2 = dat[cr - (1 << f)][f]; return min(v1, v2); } void dfs(int pos, int dep) { cnts++; cl[pos] = cnts; dist[cnts] = dep - 0; dat[cnts][0] = dep - 0; used[pos] = true; for (int i = 0; i < G[pos].size(); i++) { if (used[G[pos][i]] == true) continue; H[pos].push_back(G[pos][i]); dfs(G[pos][i], dep + 1); } cnts++; cr[pos] = cnts; dist[cnts] = dep - 1; dat[cnts][0] = dep - 1; } int getdst(int u, int v) { u = cl[u]; v = cl[v]; if (u > v) swap(u, v); return dist[u] + dist[v] - 2 * query(u, v + 1); } // クエリ平方分割 bool visited[1 << 18]; long long cnt[1 << 18]; long long dp[1 << 18], dp1[1 << 18], dp2[1 << 18]; void dfs1(int pos) { dp[pos] = cnt[pos]; for (int i = 0; i < H[pos].size(); i++) { dfs1(H[pos][i]); dp[pos] += dp[H[pos][i]]; dp1[pos] += dp1[H[pos][i]]; dp1[pos] += dp[H[pos][i]]; } } void dfs2(int pos) { long long r = 0; for (int i = 0; i < H[pos].size(); i++) { r += dp1[H[pos][i]] + dp[H[pos][i]]; } for (int i = 0; i < H[pos].size(); i++) { long long s = r - (dp1[H[pos][i]] + dp[H[pos][i]]); long long t = dp[1] - dp[H[pos][i]]; dp2[H[pos][i]] = dp2[pos] + (s + t); dfs2(H[pos][i]); } } void solve(int cl, int cr) { // Step #1. 初期化・前計算 vector vec; for (int i = 1; i <= K; i++) visited[i] = false; for (int i = 1; i <= N; i++) cnt[i] = 0; for (int i = 1; i <= N; i++) dp[i] = 0; for (int i = 1; i <= N; i++) dp1[i] = 0; for (int i = 1; i <= N; i++) dp2[i] = 0; for (int i = cl; i <= cr; i++) { if (T[i] == 1) visited[X[i]] = true; } for (int i = 1; i <= K; i++) { if (visited[i] == true) vec.push_back(i); else cnt[C[i]] += 1; } // Step #2. 全方位木 DP dfs1(1); dfs2(1); // Step #3. クエリ平方分割 for (int i = cl; i <= cr; i++) { if (T[i] == 1) { C[X[i]] = Y[i]; } if (T[i] == 2) { Answer[i] = dp1[X[i]] + dp2[X[i]]; for (int j : vec) { Answer[i] += getdst(X[i], C[j]); } } } } int main() { // Step #1. 入力 cin >> N >> K >> Q; for (int i = 1; i <= K; i++) cin >> C[i]; for (int i = 1; i <= N - 1; i++) { cin >> A[i] >> B[i]; G[A[i]].push_back(B[i]); G[B[i]].push_back(A[i]); } for (int i = 1; i <= Q; i++) { cin >> T[i]; if (T[i] == 1) cin >> X[i] >> Y[i]; if (T[i] == 2) cin >> X[i]; } // Step #2. オイラーツアー dfs(1, 0); init(); // Step #3. クエリ平方分割 int Backet = 1000; for (int i = 1; i <= Q; i += Backet) { int cl = i, cr = min(i + Backet - 1, Q); solve(cl, cr); } // Step #4. 出力 for (int i = 1; i <= Q; i++) { if (T[i] == 2) cout << Answer[i] << endl; } return 0; }