가중치가 있는 트리 가 주어진다. 트리는 번부터 번까지 번호가 붙은 개의 정점과 개의 간선으로 이루어져 있다.
처음에는 주요 정점이 하나도 없다. 이후 개의 사건이 순서대로 주어진다. 사건의 형태는 다음 두 가지 중 하나이다.
주요 정점이 개 또는 개라면 사건 의 답은 이다.
입력은 다음과 같은 형식으로 주어진다.
사건 가 주어질 때마다 정답을 한 줄에 하나씩 출력한다.
처음에는 주요 정점이 없으므로 첫 번째 출력은 이다.
정점 만 주요 정점인 경우에도 필요한 간선이 없으므로 답은 이다.
정점 와 정점 가 주요 정점인 경우 두 정점을 잇는 경로의 길이가 이므로 답은 이다.
각 ()에 대해 번 간선은 정점 와 정점 를 잇고, 길이는 이다.
각 사건은 한 줄에 하나씩 주어지며, 또는 형태이다.
추가적인 제약조건이 없다. |
이후 사건들도 같은 방식으로 현재 주요 정점들을 모두 포함하는 연결 부분그래프의 최소 간선 길이 합을 출력한다.
