有一些自己的理解不知道大家能不能看懂
1207. 大臣的旅费 - AcWing题库高质量的算法题库
https://www.acwing.com/problem/content/1209/
很久以前，TT 王国空前繁荣。
为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，TT 国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。
同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
JJ 是 TT 国重要大臣，他巡查于各大城市之间，体察民情。
所以，从一个城市马不停蹄地到另一个城市成了 JJ 最常做的事情。
他有一个钱袋，用于存放往来城市间的路费。
聪明的 JJ 发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关。
具体来说，一段连续的旅途里，第 11 千米的花费为 1111，第 22 千米的花费为 1212，第 33 千米的花费为 1313，…，第 xx 千米的花费为 x+10x+10。
也就是说，如果一段旅途的总长度为 11 千米，则刚好需要花费 1111，如果一段旅途的总长度为 22 千米，则第 11 千米花费 1111，第 22 千米花费 1212，一共需要花费 11+12=2311+12=23。
JJ 大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入格式
输入的第一行包含一个整数 nn，表示包括首都在内的 TT 王国的城市数。
城市从 11 开始依次编号，11 号城市为首都。
接下来 n−1n−1 行，描述 TT 国的高速路（TT 国的高速路一定是 n−1n−1 条）。
每行三个整数 Pi,Qi,DiPi,Qi,Di，表示城市 PiPi 和城市 QiQi 之间有一条双向高速路，长度为 DiDi 千米。
输出格式
输出一个整数，表示大臣 JJ 最多花费的路费是多少。
数据范围
1≤n≤10^ 5 1≤n≤10^5,
1≤Pi,Qi≤n1≤Pi,Qi≤n,
1≤Di≤10001≤Di≤1000
输入样例：
5
1 2 2
1 3 1
2 4 5
2 5 4
输出样例：
135本题的关键是找到最远的两个点。
所以我们需要找到一个插入点，而本题中的首都就是我们的插入点。我们可以找到一个离首都最远的点作为答案的这段路程的一个起点。当找到这个点之后我们就只要把这个点当作一个首都（把原来的首都当作一个普通的城市即可），去找一个离他最远的地方就可以了。可以这样想，假如原来的首都是A城市，找到了距离A城市最远的城市是B城市，那么我们此时吧B城市看作是一个首都之后（此时把A看作是一个普通的城市就好了），然后我们找到一个距离城市B最远的一个城市C（如果城市B,C是在城市A的两侧，这样就会很容易想通了，如果B,C在同一侧，那么很容易就可以想到城市C就是城市A了）。此时城市BC之间的距离就是本题的答案。
import java.util.*;
import java.io.*;
public class Main{
static class Node{
//存放城市的名字以及权值
int x,v;
public Node(int x,int v){
this.x = x;
this.v = v;
}
public Node(){
}
}
static int n ;
//用数组+链表的形式存储
static ArrayList<Node>[] nums = new ArrayList[100100];
//从城市a走到城市b的权值
static int[] maxs = new int[100100];
public static void main(String[] args) throws IOException{
//防止空指针异常
for(int i = 0 ; i< 100100 ; i++){
nums[i] = new ArrayList<Node>();
}
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int P,Q,D;
//输入起点，终点，权值
for(int i = 0 ; i < n - 1 ; i ++){
P = sc.nextInt();
Q = sc.nextInt();
D = sc.nextInt();
nums[P].add(new Node(Q,D));
nums[Q].add(new Node(P,D));
}
//这一步是为了找到一个离首都最远的地方，存储在maxs里面
bfs(1,-1,0);
int u = 1;
for(int i = 1 ; i <= n ; i++){
if(maxs[u] < maxs[i]){
u = i;
}
}
//找到了之后就以这个最远的地方为起点，找离他最远的地方，即本题的答案
bfs(u , -1 , 0);
for(int i = 1 ; i <= n ; i++){
if(maxs[u] < maxs[i]){
u = i;
}
}
long us = maxs[u];
long distance = (21 + us) * us / 2;
System.out.println(distance);
}
public static void bfs(int begin,int father,int value){
maxs[begin] = value;
for(Node node : nums[begin]){
if(node.x != father){//当1有两个子树2 3 把这两个遍历完即3时，由于是无向图所以他给会默认1也是3的子树，这样的话就形成了闭环，不符合本体的意思
bfs(node.x , begin , node.v + value);
}
}
}
}