6160 : Heavy Light Decomposition 기초
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리에서 특정 노드의 가중치를 변경하는 연산과 임의의 두 노드 u, v를 잇는 최단 경로 상의 모든 노드의 가중치 합을 구하는 연산을 HLD(Heavy Light Decomposition)와 세그먼트 트리를 결합하여 효율적으로 처리하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 주어집니다.
둘째 줄에 N개의 초기 가중치가 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
-
둘째 줄에 N개의 초기 가중치가 공백으로 구분되어 주어집니다.
셋째 줄부터 N-1개의 줄에 간선 정보 u, v가 주어집니다.
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
1 u val: u번 노드의 가중치를 val로 변경합니다.-
2 u v: u에서 v까지의 경로 상 노드들의 가중치 합을 구합니다.출력 설명
2번 쿼리가 주어질 때마다 해당하는 경로의 가중치 합을 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2 3 4 5
1 2
1 3
2 4
2 5
2 4 5
1 2 10
2 4 5
2 1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
0
0