DMOPC '17 Contest 4 P3 - Third Place - DMOJ: Modern Online Judge

DMOPC '17 Contest 4 P3 - Third Place

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Kirito

Problem type

Roger, Jessica, and Victor held an impromptu math contest, where Roger promptly got third place (what did you expect?). The third place prize was the second-longest path in a weighted tree with $N$ ~N~ nodes. However, when he went to collect his prize, he felt as though he had been scammed. Thus, he hires you to write a program to print the length of this path so that he may file a formal complaint to the contest organizers.

Constraints

For all subtasks:

$1 \le a_i, b_i \le N$ ~1 \le a_i, b_i \le N~

$1 \le c_i \le 10^5$ ~1 \le c_i \le 10^5~

Subtask 1 [20%]

$3 \le N \le 1\,000$ ~3 \le N \le 1\,000~

Subtask 2 [80%]

$3 \le N \le 100\,000$ ~3 \le N \le 100\,000~

Input Specification

The first line of input will contain $N$ ~N~.
The next $N-1$ ~N-1~ lines of input will contain 3 space-separated integers, $a_i\ b_i\ c_i$ ~a_i\ b_i\ c_i~, indicating there exists an edge of weight $c_i$ ~c_i~ between nodes $a_i$ ~a_i~ and $b_i$ ~b_i~.

Output Specification

A single integer, the length of the second-longest path in the tree.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Comments

1

maxcruickshanks commented on July 29, 2022, 3:09 p.m.

Since the original data were weak, a new test case was added to each subtask, and all submissions were rejudged.