题目描述

给定一棵n个点的无根树，树上的边有一个权值，要求找出一条路径使得该路径权的最小值乘边权和最大

题目来源

chty_syq的互测题

2018/7的D班集训例题

输入格式

第一行一个整数n 接下来n-1行，每行3个整数x、y、v，表示x与y之间有一条权值为v的边

输出格式

一个整数表示答案

样例数据

input

5

1 2 2

2 3 7

2 4 6

3 5 1

output

78

数据范围

->对于30%的数据，$n \leq 5000$

->对于100%的数据，$n \leq 300000$

->所有边权在[1,1000000]内