生成树 (tree)
题目描述
给定一棵 \(n\) 个节点的树。
定义这棵树的生成完全图为一个 \(n\) 个节点的完全图，图中两点 \(u,v\) 的边权为这两点在树上简单路径上的边权和。
请你求出这张完全图的最小生成树和最大生成树，分别输出两种生成树的边权之和。
输入格式
第一行输入一个正整数 \(n\).
接下来 \(n-1\) 行，每行 \(3\) 个整数 \(u,v,w\) ， 表示 \(u,v\) 之间有一条边权为 \(w\) 的边。
输出格式
一行，输出两个整数，分别表示最小生成树和最大生成树的边权和。
样例 #1
样例输入 #1
6 1 2 1 1 3 1 1 4 1 3 5 1 3 6 1样例输出 #1
5 13样例 #2
样例输入 #2
8 1 2 716487 2 3 804152 1 4 592006 3 5 613755 1 6 613771 5 7 903188 6 8 122044样例输出 #2
4365403 21539678提示
样例解释：
对于第一组样例的最大生成树，一种可行的方法是：
$1 \to 5 (2),2 \to 3 (2),2 \to 5(3) , 2 \to 6(3) ,4 \to 6(3) $ , 边权和为 \(13\).
数据范围：
Subtask0 (25pts) : \(n \le 2000\).
Subtask1 (20pts) : 保证第 \(i\) 条边连接节点 \(i\) 和 \(i+1\).
Subtask2 (20pts) : 保证第 \(i\) 条边连接节点 \(1\) 和 \(i+1\).
Subtask3 (20pts) : $n \le 2 \times10^5 $.
Subtask4 (15pts) : 无特殊限制.
对于 \(100\%\) 的数据，保证 \(1 \le n \le 10^6,1 \le w \le 10^6\)，保证输入给定的是一棵树。
本题输入量较大，请注意使用较快的读入方式。
赛时做法：一个点肯定和能到的最远的点合并，因此换根 dp 求每个点能到达的最远的点，合并的细节是并查集判断是否已经联通了， \(O(n \alpha(n))\)
正解：考虑链，发现是把树分成两部分。而对于树，就是求出直径。而对于每个点，求他和两个端点的最远的一个合并即可， \(O(n)\)