import sys from bisect import bisect_left sys.setrecursionlimit(1 << 25) def main(): import sys input = sys.stdin.read data = input().split() ptr = 0 N = int(data[ptr]) ptr += 1 K = int(data[ptr]) ptr += 1 Q = int(data[ptr]) ptr += 1 C = list(map(int, data[ptr:ptr + K])) ptr += K edges = [[] for _ in range(N + 1)] for _ in range(N - 1): a = int(data[ptr]) ptr += 1 b = int(data[ptr]) ptr += 1 edges[a].append(b) edges[b].append(a) LOG = 20 parent = [[-1] * (N + 1) for _ in range(LOG)] depth = [0] * (N + 1) in_time = [0] * (N + 1) out_time = [0] * (N + 1) time = 0 def dfs(u, p): nonlocal time in_time[u] = time time += 1 parent[0][u] = p for v in edges[u]: if v != p: depth[v] = depth[u] + 1 dfs(v, u) out_time[u] = time - 1 dfs(1, -1) for k in range(1, LOG): for v in range(1, N + 1): if parent[k-1][v] != -1: parent[k][v] = parent[k-1][parent[k-1][v]] else: parent[k][v] = -1 def lca(u, v): if in_time[u] > in_time[v]: u, v = v, u if in_time[v] <= in_time[u] <= out_time[u]: return u for k in range(LOG-1, -1, -1): if parent[k][u] != -1 and in_time[parent[k][u]] > in_time[v]: u = parent[k][u] return parent[0][u] slimes = C.copy() sum_depth_c = sum(depth[c] for c in slimes) for _ in range(Q): query = data[ptr] ptr += 1 if query == '1': p = int(data[ptr]) - 1 ptr += 1 d = int(data[ptr]) ptr += 1 old = slimes[p] sum_depth_c -= depth[old] slimes[p] = d sum_depth_c += depth[d] else: e = int(data[ptr]) ptr += 1 sum_lca = 0 u = e prev = -1 while u != -1: sum_lca += depth[u] u = parent[0][u] sum_lca = 0 u = e while u != -1: cnt_u = 0 for c in slimes: if in_time[u] <= in_time[c] <= out_time[u]: cnt_u += 1 sum_lca += depth[u] * cnt_u u = parent[0][u] total = sum_depth_c + K * depth[e] - 2 * sum_lca print(total) if __name__ == "__main__": main()