흔들리는 길의 지름
다이아몬드 II의견: 0
정점이 \(N\)개인 트리가 주어진다. 트리의 간선들은 입력에 주어진 순서대로 \(1\)번부터 \(N-1\)번까지 번호가 매겨져 있으며, 각 간선에는 가중치가 있다.
다음 형태의 갱신이 \(Q\)번 주어진다.
e w: \(e\)번 간선의 가중치를 \(w\)로 바꾼다.
각 갱신을 적용한 직후, 트리의 지름(서로 다른 두 정점을 잇는 경로 중 경로 위 간선 가중치의 합이 최대인 값)을 출력해야 한다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le u, v \le N\)이며, 주어지는 간선들은 트리를 이룬다.
\(1 \le e \le N-1\)
간선 가중치와 갱신값 \(w\)는 \(0 \le w \le 10^9\)
첫 줄에 정점의 수 \(N\)과 갱신의 수 \(Q\)가 주어진다.
이어서 \(N-1\)개의 줄에 각 간선의 두 끝점 \(u\), \(v\)와 가중치 \(w\)가 입력 순서대로 주어진다. (\(i\)번째로 주어지는 간선의 번호가 \(i\)이다.)
이어서 \(Q\)개의 줄에 갱신 \(e\), \(w\)가 한 줄에 하나씩 주어진다.
각 갱신 직후 트리의 지름을 한 줄에 하나씩 출력한다.
4 2
1 2 1
2 3 2
2 4 5
1 4
3 1
9
6트리: 1-2(1), 2-3(2), 2-4(5). 1번 간선을 4로 바꾸면 가중치는 [4,2,5]. 가장 긴 경로는 3-2-4 = 2+5 = 7. 그 다음 3번 간선을 1로 바꾸면 [4,2,1], 가장 긴 경로는 1-2-3 = 4+2 = 6.
2 2
1 2 3
1 10
1 0
10
0정점 2개, 간선 하나. 가중치를 10으로 바꾸면 지름 10, 0으로 바꾸면 지름 0이다.
riseoj 작성
출처 Original
평가 및 의견
흔들리는 길의 지름
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
흔들리는 길의 지름