可以了解一下

解题思路:

注意事项:

参考代码:

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class Main {

    static int n;

    static List<Node>[] g;//定义一个存放了node节点的邻接表 比起领接矩阵更加节省空间

    static long max = -10000000;

    static int pnt = 1;//记录端点

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();//城市数

g = new List[n + 1];

for (int i = 1; i <= n; i++) {

g[i] = new ArrayList<Main.Node>();//初始化邻接表的每一个list

}

//规定了只有n - 1条路径

for (int i = 0; i < n - 1; i++) {

int a = sc.nextInt();

int b = sc.nextInt();

int c = sc.nextInt();

g[a].add(new Node(b,c));//在编号为a的链表上添加所能到达的编号以及距离所组成的节点

g[b].add(new Node(a,c));//对称性

}

//以1为根 找到端点

//先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径

dfs(2, 2, 0);

dfs(pnt, pnt, 0);

System.out.println(dis2Money(max));

}

//from记录了从哪个点来

public static void dfs(int from,int num,long dis) {

boolean ifLeaf = true;//先假设他就是叶子节点

List<Node> neighbours = g[num];//num节点的邻居

for (int i = 0; i < neighbours.size(); i++) {

Node neighbour = neighbours.get(i);//其中一个邻居

if(neighbour.num == from)continue;

//走到这说明除了父节点还有邻居

ifLeaf = false;

dfs(num, neighbour.num, dis + neighbour.dis);

}

if (ifLeaf && dis > max) {//是叶子节点

max = dis;

pnt = num;

}

}

//推算过程 公差为d的等差数列n项和为 首项a1 加 尾项 (a1 + a1 + (n - 1) * d ) * n / 2  

public static long dis2Money(long dis) {

return 11 * dis + dis * (dis - 1) / 2;

}

static class Node{

int num;

long dis;

public Node(int num, long dis) {

super();

this.num = num;

this.dis = dis;

}

}

}