17936번 - 트리와 쿼리 13

시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB275611310.833%

문제

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
  • 데이터를 추가한 사람: taesick

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)