Yin and Yang
다이아몬드 IV의견: 0
Farmer John is planning his morning walk on the farm. The farm is structured like a tree: it has N barns (1 <= N <= 100,000) which are connected by N-1 edges such that he can reach any barn from any other. Farmer John wants to choose a path which starts and ends at two different barns, such that he does not traverse any edge twice. He also wants to choose another "rest stop" barn located on this path (which is distinct from the start or the end).
Along each edge is a herd of cows, either of the Charcolais (white hair) or the Angus (black hair) variety. Farmer John wishes to choose a path such that he will pass by an equal number of Charcolais herds and Angus herds-- both on the way from the start to his rest stop, and on the way from the rest stop to the end.
Farmer John is curious how many different paths he can choose that are "balanced" as described above. Two paths are different only if they consist of different sets of edges; a path should be counted only once even if there are multiple valid "rest stop" locations along the path that make it balanced.
Line 1: The integer N.
Lines 2..N: Three integers a_i, b_i and t_i, representing the two barns that edge i connects. t_i is 0 if the herd along that edge is Charcolais, and 1 if the herd is Angus.
One integer, representing the number of possible paths Farmer John can choose from.
yinyang.inyinyang.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.
평가 및 의견
Yin and Yang
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Yin and Yang