6165 : 트리 마스터
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치가 있는 트리에서 간선의 가중치를 변경하는 연산과 임의의 두 노드 u, v 사이 경로 상에 있는 간선의 최대 가중치를 구하는 연산을 효율적으로 처리하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N과 쿼리의 개수 Q (1 ≤ N, Q ≤ 100,000)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v와 그 가중치 w가 주어집니다. (간선 번호는 입력된 순서대로 1번부터 N-1번까지 매겨집니다.)
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
-
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v와 그 가중치 w가 주어집니다. (간선 번호는 입력된 순서대로 1번부터 N-1번까지 매겨집니다.)
그 다음 Q개의 줄에 쿼리가 주어집니다.
-
1 i val: i번째 간선의 가중치를 val로 변경합니다.-
2 u v: u에서 v까지의 경로 상의 간선 가중치 중 최댓값을 구합니다. (u = v인 경우 경로는 간선을 포함하지 않으므로 0을 출력합니다.)출력 설명
2번 쿼리가 주어질 때마다 경로 상의 최대 간선 가중치를 한 줄씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 4
1 2 3
1 3 4
3 4 2
3 5 6
2 4 5
1 2 10
2 4 5
2 1 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
0
0