Coding is the closest thing we have to a surperpower

3541 : 树进阶-练习-树的直径2
描述

给一棵n个节点的树, 节点编号为1~n，每条边有权值。

对于一棵树，最长的路径为树的直径，可能不唯一。

求该树的直径长度是多少，以及有多少条边满足所有的直径都经过该边。

输入

第一行输入两个整数n(1≤n≤2⋅105)n(1 \le n \le 2 \cdot 10^5)。

接下来n-1行，每行三个整数xi,yi(1≤xi,yi≤n,xi≠yi),wi(1≤wi≤1000)x_i, y_i (1 \le x_i, y_i \le n, x_i \ne y_i), w_i(1 \le w_i \le 1000), 表示xi,yix_i, y_i​之间有一条边，其边权为wiw_i。

输入保证是一棵树。

输出

共两行。第一行一个整数，表示直径的长度。第二行一个整数，表示被所有直径经过的边的数量。

样例

输入
复制

6 
3 1 1000 
1 4 10 
4 2 100 
4 5 50 
4 6 100

输出
复制

1110
2
标签
树
语言：
主题：
登录以提交代码;