시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 1024 MB 83 20 14 31.818%

문제

다른 문제의 난이도가 너무 높은 것에 경악한 브루는, 자신과 같은 낮은 실력의 참가자들도 즐길 수 있는 문제를 만들기로 결심했다.

트리가 주어진다. 아래 두 가지 쿼리를 처리하여라.

  • 1 k x: k번 간선의 길이를 x로 바꾼다.
  • 2 p: p번 정점을 지나는 가장 긴 단순 경로의 길이를 출력한다.

단순 경로란, 한 정점을 두 번 이상 지나지 않는 경로를 의미한다.

정점의 번호는 1부터 시작한다.

입력

첫 줄에 트리의 정점의 개수 N과 쿼리의 개수 Q가 주어진다. (2 ≤ N, Q ≤ 150,000)

둘째 줄부터 N번째 줄까지 N-1개의 줄에는, 1번 간선부터 N-1번 간선까지의 정보가 차례대로 주어진다. 즉, 각 간선에 대해, 간선이 연결하는 두 정점의 번호 ui, vi, 그리고 간선의 길이 di가 차례로 주어진다. (1 ≤ ui, vi ≤ N, ui ≠ vi, 1 ≤ di ≤ 109)

N+1번째 줄부터 N+Q번째 줄까지는 쿼리가 주어진다. 쿼리는 위에서 설명한 두 종류 중 하나이다. (1 ≤ k < N, 1 ≤ x ≤ 109, 1 ≤ p ≤ N)

입력으로 주어지는 트리는 올바른 트리임이 보장된다. 또, 2번 쿼리가 하나 이상 주어짐이 보장된다.

출력

모든 2번 쿼리에 대해, 각 쿼리의 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

6 6
1 3 3
2 3 2
3 4 4
4 5 1
4 6 6
2 5
1 2 4
2 5
1 2 2
1 3 1
2 5

예제 출력 1

8
9
7

트리의 초기 상태는 아래와 같다.

이때 5번 정점을 지나는 가장 긴 경로는 1번 정점에서 5번 정점까지의 경로로, 길이는 8이다.

두 번째 쿼리 이후, 트리는 아래와 같다.

이때 5번 정점을 지나는 가장 긴 경로는 2번 정점에서 5번 정점까지의 경로로, 길이는 9이다.

모든 수정 쿼리 이후, 트리의 상태는 아래와 같다.

이때 5번 정점을 지나는 가장 긴 경로는 5번 정점에서 6번 정점까지의 경로로, 길이는 7이다.

출처

High School > 서울과학고등학교 > 2020 SciOI #1 H번

  • 문제를 만든 사람: 79brue