문제
루트가 정점 1인 N개의 정점으로 이루어진 트리가 주어진다. 1번 정점이 이 트리의 루트이다.
트리의 각 간선은 무거운 간선(heavy edge) 또는 가벼운 간선(light edge) 중 하나이다. 각 정점에 대해 해당 정점과 그 자식들을 연결하는 간선 중 최대 하나가 무거운 간선일 수 있다는 트리의 Heavy-Light Decomposition에 대해 고려하자.
이 문제에서는 초기에 비어 있는 간선 집합 T가 있다. 이때 T에는 중복된 간선이 존재할 수 있다.
각각의 업데이트가 수행될 때마다, 여러분의 작업은 T에 존재하는의 모든 간선 중, 가벼운 간선의 개수의 합을 최소화하도록 무거운 간선과 가벼운 간선을 할당하는 것이다.
총 Q번의 업데이트가 주어진다. 각 쿼리는 세 개의 정수 s, e, k로 이루어져 있으며, 이는 s에서 e로 가는 단순 경로를 k번 복사하여 T에 삽입한다는 것을 의미한다. 각 업데이트 후에 T에 속한 간선 중, 가벼운 간선의 최소 개수를 찾아라.
입력
첫 줄에 정점의 개수 N과 쿼리의 개수 Q가 주어진다. (2<=N<=100000, 1<=Q<=100000)
그 다음 N-1개의 줄에 걸쳐 트리의 간선에 대한 정보가 주어진다.
그 다음 Q개의 줄에 걸쳐 각 쿼리를 표현하는 세개의 정수 s, e, k가 주어진다. (1<=s, e<=N, 1<=k<=10^9)
출력
각 쿼리 이후 T에 속한 간선 중, 가벼운 간선의 최소 개수를 줄바꿈으로 구분하여 출력하여라.
예제 #1
3 3
1 2
3 1
1 3 2
1 3 3
1 2 2
0
0
2
예제 #2
8 8
4 6
8 4
1 6
5 1
2 1
3 2
7 3
2 7 1
8 2 1
5 3 6
8 3 5
1 4 2
6 7 1
5 6 4
6 2 3
0
1
7
12
14
15
23
26
예제 #3
8 10
8 2
7 8
1 2
4 2
5 1
6 2
3 7
4 5 4
7 2 5
5 8 7
1 3 7
3 2 3
6 8 4
7 3 4
6 7 6
4 8 3
1 3 2
4
8
15
15
15
19
19
25
28
28
출처
KAIST ICPC Mock 2023
로그인해야 코드를 작성할 수 있어요.