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