P3085 [USACO13OPEN] Yin and Yang G

Farmer John is planning his morning walk on the farm. The farm is structured like a tree: it has N barns (1

\* 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.

\* Line 1: One integer, representing the number of possible paths Farmer John can choose from.

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. 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.