DMOPC '23 Contest 1 P4 - Wandering Walk

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem types

Edward is wandering around in Schenley Park in hopes of coming up with new problem ideas for DMOPC. The park can be modeled as a set of N junctions numbered from 1 to N connected by N-1 roads such that there is exactly one path between any two junctions. Edward may choose to begin his walk from any junction, and during his walk he will repeatedly choose an adjacent road to walk on until he reaches the neighbouring junction. For convenience, we say that the length of his walk is simply the number of roads he passes through. Edward would love to wander forever to generate as many ideas as possible, but there is one problem: the roads often have benches where people may sit and observe passersby! Due to his social anxiety, he does not want to look like a wandering weirdo to the people on the benches and will restrict himself to walking along the road connecting junctions a_i and b_i at most c_i times. Given this condition, what is the length of the longest possible walk through the park?


1 \le N \le 10^6

1 \le a_i, b_i \le N

1 \le c_i \le 10^9

Subtask 1 [5%]

c_i is even for all i.

Subtask 2 [10%]

a_i = 1 for all i.

Subtask 3 [20%]

a_i + 1 = b_i for all i.

Subtask 4 [25%]

1 \le N \le 3 \times 10^3

Subtask 5 [40%]

No additional constraints.

Input Specification

The first line contains the integer N.

The next N-1 lines each contain 3 integers a_i, b_i, and c_i.

Output Specification

Output a single integer, the length of the longest possible walk through the park.

Sample Input

1 2 3
1 3 1
3 4 2
3 5 3
4 6 1
4 7 1

Sample Output


Explanation for Sample

Edward can walk through the junctions in the following order: 2, 1, 2, 1, 3, 5, 3, 4, 3, 5. This is a walk of length 9, and it can be proven that no longer walk exists.


There are no comments at the moment.