DMOPC '17 Contest 4 P3 - Third Place - Olympiads 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 \leq a_{i}, b_{i} \leq N$

$1 \le c_i \le 10^5$ $1 \leq c_{i} \leq 10^{5}$

Subtask 1 [20%]

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

Subtask 2 [80%]

$3 \le N \le 100\,000$ $3 \leq N \leq 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

Copy

Sample Output 1

Copy

Sample Input 2

Copy

Sample Output 2

Copy

Comments

0

sre0x2a commented 44 days ago ← edit 2 →

This one is tough

2

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.