시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

N개의 정점으로 이루어진 루트 있는 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다. i번 정점은 가중치 Ai를 가지고 있다. 초기에는 r번 정점이 루트이다. 

아래의 쿼리를 수행하는 프로그램을 작성하시오.

  • 0 x y: x의 서브트리에 있는 정점들의 가중치를 y로 바꾼다.
  • 1 r: 트리의 루트를 r로 바꾼다.
  • 2 x y z: x와 y를 잇는 경로에 있는 정점들의 가중치를 z로 바꾼다.
  • 3 x: x의 서브트리에 있는 정점들의 가중치의 최솟값을 출력한다.
  • 4 x: x의 서브트리에 있는 정점들의 가중치의 최댓값을 출력한다.
  • 5 x y: x의 서브트리에 있는 정점들의 가중치를 y만큼 더한다.
  • 6 x y z: x와 y를 잇는 경로에 있는 정점들의 가중치를 z만큼 더한다.
  • 7 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 최솟값을 출력한다.
  • 8 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 최댓값을 출력한다.
  • 9 x y: x의 부모를 y로 바꾼다. 만약 x의 서브트리 안에 정점 y가 존재한다면 이 쿼리를 무시한다.
  • 10 x y: x와 y를 잇는 경로에 있는 정점들의 가중치의 합을 출력한다.
  • 11 x: x의 서브트리에 있는 정점들의 가중치의 합을 출력한다.

입력

첫 번째 줄에 두 정수 N, M 이 주어진다. (1 ≤ N, M ≤ 105)

이후 N-1개의 줄에는 각 간선이 연결하는 두 정점 번호 u, v가 주어진다. (1 ≤ u, v ≤ N)

이후 N개의 줄에 i번 정점의 가중치 Ai 가 주어진다.

이후 초기 루트의 정점 번호 r이 주어진다. (1 ≤ r ≤ N)

이후 M개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다. 

입력으로 주어지는 모든 정수는 C++ int 형으로 표현될 수 있으며, 쿼리를 처리하는 도중, 모든 정점의 가중치의 합이 int 범위를 초과하지 않도록 입력이 주어진다.

출력

각각의 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1

예제 출력 1

9
1
1

예제 입력 2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

예제 출력 2

173
860
103
791
608
1557

출처

  • 문제를 번역한 사람: koosaga