#USACO MooTube

문제링크

Description : 

N(<=10만)개의 노드를 가진 가중치가 있는 트리가 입력으로 주어졌을 때 Q(<=10만)개의 쿼리를 처리하는 문제

각 쿼리는 가중치 K,정점번호 V로 이루어져 있고 K이하의 가중치를 가지는 간선들을 이용해서 V에서 출발해서 몇개의 정점을 거칠 수 있는지 묻는다.

Sol : 

오프라인 풀이(Disjoint set)

쿼리와 간선들을 가중치순서로 정렬한 다음, 각 쿼리보다 작은 가중치를 가지는 간선들에 대해 union을 해준 후, v가 속한 집합의 크기가 쿼리의 답이다.

정답 코드