USACO 2013 US Open, Gold
Problem 2. Yin and Yang
Contest has ended.
Log in to allow submissions in analysis mode
Problem 2: Yin and Yang [Nathan Pinsker, 2013]
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 worries that his
path might be a little long, so 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. Being the wise man that he is,
Farmer John wants to balance the forces of yin and yang that weigh upon his
walk. To do so, he 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.
Please help determine the number of paths Farmer John can choose!
PROBLEM NAME: yinyang
INPUT FORMAT:
* 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.
SAMPLE INPUT (file yinyang.in):
7
1 2 0
3 1 1
2 4 0
5 2 0
6 3 1
5 7 1
INPUT DETAILS:
There are 7 barns and 6 edges. The edges from 1 to 2, 2 to 4 and 2 to 5 have
Charcolais herds along them.
OUTPUT FORMAT:
* Line 1: One integer, representing the number of possible paths
Farmer John can choose from.
SAMPLE OUTPUT (file yinyang.out):
1
OUTPUT DETAILS:
No path of length 2 can have a suitable rest stop on it, so we can only
consider paths of length 4. The only path that has a suitable rest stop is
3-1-2-5-7, with a rest stop at 2.
Contest has ended. No further submissions allowed.