33844번 - 트리와 색깔과 쿼리

문제

$N$개의 정점으로 구성된 트리가 주어진다. 각 정점에는 1ドル$번부터 $N$번까지 번호가 붙어 있고, 1ドル$번 정점은 트리의 루트이다. 추가로 각 정점은 색깔 $A_i$를 가지고 있다. 정점의 색깔은 1ドル$ 이상 50ドル\ 000$ 이하의 정수로 나타내어진다.

다음 세 가지 쿼리를 수행하는 프로그램을 작성하시오. $P = P_0, P_1, \cdots, P_N$는 0ドル$부터 $N$까지의 정수가 한 번씩 등장하는 순열이며, 입력에서 주어진다.

• 1 $x$: 정점 $x$를 루트로 하는 서브트리에 색깔이 $i$인 정점의 수를 $C_i$라고 할 때 $\sum i \cdot P_{C_i}$를 출력한다.
• 2 $x$ $y$: 두 정점 $x$와 $y$를 잇는 경로에 색깔이 $i$인 정점의 수를 $C_i$라고 할 때 $\sum i \cdot P_{C_i}$를 출력한다.
• 3 $x$ $z$: 정점 $x$의 색깔을 $z$로 바꾼다.

입력

첫 번째 줄에 정수 $N,ドル $Q$가 공백으로 구분되어 주어진다. $(2\le N, Q\le 50\ 000)$

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1\le A_i\le 50\ 000)$

세 번째 줄에 $N$개의 정수 $P_1, P_2, \cdots, P_N$이 공백으로 구분되어 주어진다. $P_0 = 0$이며, $P$는 순열이다.

네 번째 줄부터 $N-1$개의 줄에 걸쳐 트리에서 $i$번째 간선이 연결하는 두 정점 번호 $u_i, v_i$가 공백으로 구분되어 주어진다. $(1\le u_i,v_i\le N)$

이어서 $Q$개의 줄에 각 쿼리가 다음 형식 중 하나로 주어진다. $(1\le x, y\le N;$ 1ドル\le z\le 50\ 000;$ $x, y, z$는 정수$)$

• 1 $x$
• 2 $x$ $y$
• 3 $x$ $z$

출력

1ドル$번과 2ドル$번 쿼리의 결과를 한 줄에 하나씩 출력한다. 1ドル$번 혹은 2ドル$번 쿼리가 1ドル$개 이상 주어짐이 보장된다.

제한

힌트