UOJ Logo 蜗牛编程训练题库

JZOJ

#1292. 树的中心

Statistics
时间限制:1s    空间限制:64MB    输入文件:tree.in    输出文件:tree.out
当前24小时内您还剩30次提交本题的机会

题目描述

给定一棵树,树中包含 $n$ 个结点(编号$1$~$n$)和 $n-1$ 条无向边,每条边都有一个权值。

请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。

输入格式

第一行包含整数 $n$。

接下来 $n-1$ 行,每行包含三个整数 $a_i,b_i,c_i$,表示点 $a_i$ 和 $b_i$ 之间存在一条权值为 $c_i$ 的边。

输出格式

输出一个整数,表示所求点到树中其他结点的最远距离。

样例

输入样例
5 
2 1 1 
3 2 1 
4 3 1 
5 1 1
输出样例
2

数据范围与提示

对于 $30 \%$ 的数据, $1 \leq n \leq 100$;

对于 $100\%$ 的数据, $1 \le n \le 10000$, $1 \le a_i,b_i \le n$, $1 \le c_i \le 10^5$ 。

Solutions

标题 发表者 发表日期
None