8056 : 트리 경로 가중치 쿼리
•시간제한: 3.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 노드로 이루어진 트리가 주어집니다. 각 노드 $i$는 초기 가중치 $v_i$를 가집니다. 루트 노드는 항상 $1$번 노드입니다.
다음 두 가지 쿼리를 효율적으로 처리하는 프로그램을 작성하십시오.
- `1 s x`: 노드 $s$의 가중치를 $x$로 변경합니다.
- `2 u`: 루트($1$번 노드)에서 노드 $u$까지의 경로 상에 있는 모든 노드의 가중치 합을 출력합니다.
[제약 조건]
• $1 \le N, Q \le 200{,}000$
• $1 \le v_i \le 10^9$
• $1 \le a, b \le N$
• $1 \le s, u \le N$, $1 \le x \le 10^9$
다음 두 가지 쿼리를 효율적으로 처리하는 프로그램을 작성하십시오.
- `1 s x`: 노드 $s$의 가중치를 $x$로 변경합니다.
- `2 u`: 루트($1$번 노드)에서 노드 $u$까지의 경로 상에 있는 모든 노드의 가중치 합을 출력합니다.
[제약 조건]
• $1 \le N, Q \le 200{,}000$
• $1 \le v_i \le 10^9$
• $1 \le a, b \le N$
• $1 \le s, u \le N$, $1 \le x \le 10^9$
입력 설명
첫째 줄에 노드의 수 $N$과 질의의 수 $Q$가 공백으로 구분되어 주어집니다. ($1 \le N, Q \le 200{,}000$)
둘째 줄에 각 노드의 초기 가중치 $v_1, v_2, \dots, v_N$이 공백으로 구분되어 주어집니다. ($1 \le v_i \le 10^9$)
다음 $N-1$개의 줄에 트리의 간선을 나타내는 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
다음 $Q$개의 줄에 걸쳐 질의 정보가 주어집니다. 각 질의는 `1 s x` 또는 `2 u` 형식입니다. ($1 \le s, u \le N, 1 \le x \le 10^9$)
둘째 줄에 각 노드의 초기 가중치 $v_1, v_2, \dots, v_N$이 공백으로 구분되어 주어집니다. ($1 \le v_i \le 10^9$)
다음 $N-1$개의 줄에 트리의 간선을 나타내는 두 노드 $a, b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le N$)
다음 $Q$개의 줄에 걸쳐 질의 정보가 주어집니다. 각 질의는 `1 s x` 또는 `2 u` 형식입니다. ($1 \le s, u \le N, 1 \le x \le 10^9$)
출력 설명
각 `2 u` 질의에 대해 가중치 합을 한 줄에 하나씩 순서대로 출력합니다. (가중치 합은 64비트 정수 범위를 가질 수 있습니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
4 2 5 2 1
1 2
1 3
2 4
3 5
1 3 10
2 4
2 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8
15도움
오일러 경로 테크닉(Euler Tour Technique)을 사용하여 트리를 구간(배열)으로 변환합니다. 노드 $s$의 가중치 변경 $x$는 $s$의 서브트리 구간 `[in[s], out[s]]` 전체에 더해지는 가중치 변화량($x - v_s$)의 구간 갱신에 대응됩니다. 펜윅 트리(BIT)를 이용하여 구간 업데이트 및 점 쿼리를 $O(\log N)$에 처리할 수 있습니다.