좀비로드

문제 정보

문제

전대프국에 좀비가 나타났다!!! 2014년 12월에 처음 발견된 좀비는 이후 꾸준히 확산되어, 2015년 1월에는 전대프국의 교통을 마비시켜 버렸다.
"헐, 나 졸업식 가야 되는데...?!"
2015년 2월 졸업식을 앞둔 태윤이는 학교 가는 길이 좀비 때문에 끊겨버린 것을 알게 되었다.
'나 말고도 학교 가는 길이 끊어진 전대프국 사람들이 있지 않을까?'
과연 그랬다. 학교 가는 길은 물론이요, 이제 더 이상 모두가 한 자리에 모일 수 없게 되었고, 전대프연 대회도 열릴 수 없게 되었다. 그래서 대회(기념품?)에 목마른 전대프국 사람들은 좀비들을 퇴치하기로 결의했다.
전대프국은 정점과 간선으로 이루어진 하나의 트리 형태로 생겼다. 현재 몇몇 간선은 좀비에게 점령 당한 상태이고, 이렇게 점령된 간선을 좀비로드라고 부른다. 좀비에게 점령되지 않은 모든 간선에는 전대프국 사람들이 살고 있고, 이런 간선을 생존로드라고 부른다. 전대프국 사람들이 서로 한 자리에 모이기 위해서 점령해야 할 좀비로드의 최소 개수를 구하라.

입력

입력은 T 개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 T가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 개수 N이 주어진다. (3 \le N \le 20000) 그 다음 N-1줄에 각각 간선의 정보로써 인접한 두 정점의 번호 V_i, U_i와 좀비로드 여부를 나타내는 Z_i가 주어진다. (0 \le V_i, U_i < N, 0 \le Z_i \le 1) Z_i가 1이면 좀비로드, 0이면 생존로드임을 의미한다.

각 테스트 케이스에 대해, 생존로드는 하나 이상 존재한다.

출력

각 테스트 케이스마다 전대프국 사람들이 점령해야 할 좀비로드의 최소 개수를 출력한다.

예제 입력

3
5
0 1 1
0 2 0
3 1 0
4 1 1
6
0 1 1
0 3 0
0 4 1
2 1 1
4 5 1
7
0 1 1
0 2 1
3 1 1
4 1 0
2 5 1
2 6 0

예제 출력

1
0
2

노트

2개의 댓글이 있습니다.