만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

포도나무

시간 제한3초메모리 제한1024 MB

요약
가중치가 있는 트리에서 정점에 포도를 올리고 떼며 간선 길이를 바꿀 때, 주어진 정점에서 가장 가까운 포도가 있는 정점까지의 거리를 구합니다.
난이도

어려움10점 중 8점

유형
트리, 분할 정복, 최단 경로
정답자
아직 제출이 없습니다

문제

Syrup the Turtle이 마을을 휘감으며 자라는 거대한 포도나무에 물을 준다. 포도나무에는 1부터 NN까지 번호가 붙은 NN개의 잎이 달린 마디와, 1부터 N−1N - 1까지 번호가 붙은 N−1N - 1개의 가지가 있다. ii번째 가지는 마디 AiA_i와 BiB_i를 직접 잇고, 길이는 WiW_i이다. 같은 두 마디를 직접 잇는 가지는 없으며, 모든 마디는 가지를 따라 직접 또는 간접으로 연결되어 있다.

Syrup은 포도나무를 다음과 같이 바꾸거나 조회할 수 있다.

  • 마디 uu에 물을 준다(soak). 빈 마디였다면 즉시 큰 포도 한 알이 열리고, 포도가 있었다면 그 포도가 떨어진다.
  • 마디 aa와 bb 사이 가지의 길이를 ww로 바꾼다(anneal).
  • 마디 qq에서 가장 가까운 포도를 찾는다(seek). 거리는 qq에서 포도가 달린 마디까지 가는 최단 경로의 길이다.

처음에는 포도나무에 포도가 없다. QQ개의 행동을 순서대로 처리하고, 각 seek의 답을 구하라.

입력

첫 줄에 NN과 QQ가 주어진다.

이어서 N−1N - 1개의 줄에 각각 AiA_i, BiB_i, WiW_i가 주어진다.

이어서 QQ개의 줄에 행동이 하나씩 주어진다.

  • 1 q: 마디 qq에서 가장 가까운 포도를 찾는다.
  • 2 u: 마디 uu에 물을 준다.
  • 3 a b w: 마디 aa와 bb 사이 가지의 길이를 ww로 바꾼다. 이 가지는 반드시 존재한다.

출력

각 seek 행동마다 가장 가까운 포도까지의 거리를 한 줄에 출력한다. 포도가 없으면 −1-1을 출력한다.

제한

  • 2≤N≤1000002 \le N \le 100000
  • 1≤Q≤1000001 \le Q \le 100000
  • 1≤Ai≠Bi≤N1 \le A_i \ne B_i \le N
  • 0≤Wi≤1090 \le W_i \le 10^9

예제3

  1. 예제 1

    입력
    7 11
1 2 2
2 3 4
5 6 1
5 3 6
3 7 6
2 4 9
2 6
2 4
2 7
1 1
3 2 3 0
1 1
3 6 5 0
1 1
3 3 5 0
3 2 4 0
1 1
    예상 출력
    11
8
8
2

  2. 예제 2

    입력
    6 11
1 2 3
1 3 4
2 4 1
2 5 4
3 6 6
2 3
1 2
2 4
3 1 3 2
1 1
2 3
3 2 1 2
2 4
1 3
2 2
1 3
    예상 출력
    7
2
-1
4

  3. 예제 3

    입력
    7 8
1 2 2
2 3 3
3 6 2
4 6 1
5 6 4
6 7 3
2 3
1 4
2 3
2 5
1 1
3 6 7 4
1 5
1 7
    예상 출력
    3
11
0
8