An Animal Contest 1 P5 - Odd Alpacas

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem type

It is a well-known fact that alpacas love numbers. The reason behind this fascination is uncertain, but that shouldn't be your concern at the moment. You've stumbled upon a herd of alpacas living in N connected villages, joined by N - 1 bidirectional roads of length w_i.

Let us define x as the number of even length pathways between any two villages and y as the number of odd length pathways between any two villages. The length of a pathway between u_i and v_i is defined as the sum of the road lengths connecting u_i and v_i.

You look up and find yourself face to face with the queen alpaca and she's angry. She orders you to tell her the minimum value of |x - y| given that you can change the length of at most 1 road. Fail to do so and you'll be turned into an alpaca. Can you make it out alive?

Constraints

1 \le N \le 2 \cdot 10^5

1 \le w_i \le 10^4

1 \le u_i, v_i \le N

Subtask 1 [10%]

1 \le N \le 200

Subtask 2 [20%]

1 \le N \le 2 \cdot 10^3

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line of input will contain the integer N, the number of villages.

The next N - 1 lines will contain the integers u_i, v_i, and w_i, representing a bidirectional road between u_i and v_i that is w_i units long.

Output Specification

Output the minimal possible value of |x - y| after modifying the length of at most one edge.

Note that 64-bit integers may be required.

Sample Input 1

5
5 3 97
4 2 21
1 2 49
3 2 4

Sample Output 1

2

Explanation for Sample Output 1

An optimal solution is not changing any lengths.

In the original graph, there are 6 pairs of villages which form a path of odd length:

  • (1 - 2) of length 49.
  • (1 - 3) of length 53.
  • (2 - 4) of length 21.
  • (2 - 5) of length 101.
  • (3 - 4) of length 25.
  • (3 - 5) of length 97.

Furthermore there are 4 pairs of villages which form a path of even length.

  • (1 - 4) of length 70.
  • (1 - 5) of length 150.
  • (2 - 3) of length 4.
  • (4 - 5) of length 122.

Thus, the answer is |6 - 4| = 2.

Sample Input 2

6
6 1 100
2 1 86
4 3 12
3 2 40
5 2 44

Sample Output 2

1


Comments

There are no comments at the moment.