레이팅 미적용농부 존(Farmer John)은 농장에서의 아침 산책을 계획하고 있다. 농장은 트리 구조이다. N개 (1 <= N <= 100,000)의 헛간이 N-1개의 간선으로 연결되어 있어, 어느 헛간에서든 다른 어느 헛간으로도 갈 수 있다. 농부 존은 서로 다른 두 헛간에서 시작하고 끝나는 경로를 골라, 어떤 간선도 두 번 지나지 않으려 한다. 또한 이 경로 위에 있는 (시작점이나 끝점과는 다른) "쉼터" 헛간도 하나 고르고 싶어 한다.
각 간선을 따라 샤롤레(흰 털) 또는 앵거스(검은 털) 품종의 소 무리가 있다. 농부 존은 시작점에서 쉼터까지 가는 길과 쉼터에서 끝점까지 가는 길 모두에서, 지나치는 샤롤레 무리와 앵거스 무리의 수가 같은 경로를 고르고 싶어 한다.
농부 존은 위와 같이 "균형 잡힌" 경로를 몇 가지나 고를 수 있는지 궁금해한다. 두 경로는 서로 다른 간선 집합으로 이루어진 경우에만 다르다. 경로를 균형 잡히게 만드는 유효한 "쉼터" 위치가 여러 개 있더라도 경로는 한 번만 세어야 한다.
첫째 줄: 정수 N.
둘째 줄부터 N번째 줄까지: 간선 i가 연결하는 두 헛간을 나타내는 세 정수 a_i, b_i, t_i가 주어진다. t_i는 그 간선을 따라 있는 무리가 샤롤레이면 0, 앵거스이면 1이다.
농부 존이 고를 수 있는 가능한 경로의 수를 나타내는 정수 하나.
yinyang.in · 출력을 쓸 파일 yinyang.out7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 11Output details: The only path with a suitable rest stop is 3-1-2-5-7, with a rest stop at 2.