루트가 정점 1인 N개의 정점으로 이루어진 트리가 주어진다. 1번 정점이 이 트리의 루트이다.

트리의 각 간선은 무거운 간선(heavy edge) 또는 가벼운 간선(light edge) 중 하나이다. 각 정점에 대해 해당 정점과 그 자식들을 연결하는 간선 중 최대 하나가 무거운 간선일 수 있다는 트리의 Heavy-Light Decomposition에 대해 고려하자.

이 문제에서는 초기에 비어 있는 간선 집합 T가 있다. 이때 T에는 중복된 간선이 존재할 수 있다.

각각의 업데이트가 수행될 때마다, 여러분의 작업은 T에 존재하는의 모든 간선 중, 가벼운 간선의 개수의 합을 최소화하도록 무거운 간선과 가벼운 간선을 할당하는 것이다.

총 Q번의 업데이트가 주어진다. 각 쿼리는 세 개의 정수 s, e, k로 이루어져 있으며, 이는 s에서 e로 가는 단순 경로를 k번 복사하여 T에 삽입한다는 것을 의미한다. 각 업데이트 후에 T에 속한 간선 중, 가벼운 간선의 최소 개수를 찾아라.

#6132 upload 5 done 4 how_to_reg 1

HLD timer 5s memory 1024MB

#6132

HLD 5s 1024MB