페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3608

트리와 쿼리 3 1s 128MB

문제

노드가 N개 있고, 간선에 가중치가 있는 트리가 있다. 나올 수 있는 쿼리는 다음과 같다.

 

쿼리 1: E번 간선의 가중치를 X로 바꾼다.

쿼리 2: A번 노드에서 B번 노드로 가는 경로에 존재하는 간선의 가중치 중 최댓값을 출력한다.

 

두 종류의 쿼리를 빠르게 수행하는 프로그램을 작성하여라.​ 


입력

첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 100,000)가 주어진다.

 

두 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호와, 그 간선의 가중치 w_i가 주어진다. (0 ≤ w_i ≤ 10^9)

 

N+1번째 줄에는 쿼리의 수 Q (1 ≤ Q ≤ 100,000)가 주어진다.

 

N+2번째 줄부터 Q개의 줄에는 쿼리가 주어진다.

쿼리 1은 1 E X로, 쿼리 2는 2 A B로 주어진다. (1 ≤ E ≤ N-1, 0 ≤ X ≤ 10^9, 1 ≤ A, B ≤ N)

 


출력

쿼리 2의 정답을 한 줄에 하나씩 출력한다.

채점 데이터에서 쿼리 2는 항상 하나 이상 존재한다.

 


예제 

5

1 2 2

2 3 3

3 4 2

2 5 1

4

2 1 5

1 4 5

2 1 5

2 1 3
2

5

3

로그인해야 코드를 작성할 수 있어요.