Cost Of Subtree

Time limit1sMemory limit512 MB

Summary
Given a tree with weighted edges, find a non-empty connected edge set maximizing its edge count times the minimum edge weight in it.
Level

Hard8 of 10

Topics
Tree, Union-find, Sorting, Greedy
Solved
No attempts yet

Problem

A valuable tree with nn vertices grows near Byteazar's house. Edge ii has cost viv_i assigned to it.

A subtree of the tree is a non-empty connected subset of its edges.

The cost of a subtree is the number of edges in the subtree multiplied by the lowest value of viv_i in it.

Byteazar wants to make some money by selling subtrees, so he wants to know the maximum cost of a subtree of his tree.

Input

The first line contains a single integer nn (2≤n≤1052 \le n \le 10^5), the number of vertices in the tree. Each of the following n−1n-1 lines contains three integers aia_i, bib_i and viv_i (1≤ai,bi≤n1 \le a_i, b_i \le n; ai≠bia_i \ne b_i; 1≤vi≤1091 \le v_i \le 10^9), the vertices connected by the edge and its cost.

Output

Print one integer, the maximum cost of a subtree of the given tree.

Examples2

  1. Example 1

    Input
    10
6 4 8
5 6 7
2 3 5
3 1 2
2 7 3
9 7 4
8 2 6
8 10 7
6 2 4
    Expected output
    24

  2. Example 2

    Input
    6
1 3 12
5 3 4
3 4 2
2 4 5
6 2 6
    Expected output
    12