题目地址：

https://www.lintcode.com/problem/second-diameter/description

给定一棵树型的无向带权图，求其次大直径（即所有两点距离$d(v_1,v_2)$里第二大的，相等的距离也要参与计数）。

先求最大直径（第一直径）的两个端点$v_1$和$v_2$，则${\max }_{u\ne v_2}d(v_1,u)$和${\max }_{u\ne v_1}d(v_2,u)$的最大值即为所求。而求最远点距离可以用BFS来做（主要是为了防止DFS爆栈）。

算法正确性证明：
首先，参考https://blog.csdn.net/qq_46105170/article/details/108374199可知从任意点出发找到的最远距离的点一定是直径的一个端点，那么第二直径一定有某个点不是$v_1$或者$v_2$，但是第二直径的非第一直径的端点的那个端点出发，最远距离一定是到达了直径的某个端点的，换言之，第二直径可以从第一直径的某个端点出发，搜到最远的非$v_1$或者$v_2$的点的距离，就是第二直径长度。

代码如下：

import java.util.*;public class Solution {private long res;/*** @param edge: edge[i][0] [1] [2]  start point,end point,value* @return: return the second diameter length of the tree*/public long getSecondDiameter(int[][] edge) {// write your code here// 顶点数是边数加1int n = edge.length + 1;Map<Integer, List<int[]>> graph = buildGraph(edge);// 先找到直径的两个端点int far1 = bfs(0, graph, -1, new boolean[n]);int far2 = bfs(far1, graph, -1, new boolean[n]);// 然后分别从两个端点出发，计算除去另一个端点的情况下的最远距离bfs(far1, graph, far2, new boolean[n]);bfs(far2, graph, far1, new boolean[n]);return res;}// 返回与v离得最远的，但不是u的点的编号。同时当u不是直径端点的时候，更新resprivate int bfs(int v, Map<Integer, List<int[]>> graph, int u, boolean[] visited) {Queue<long[]> queue = new LinkedList<>();queue.offer(new long[]{v, 0});visited[v] = true;// farV存离v最远的点（可能要排除u）int farV = v;// 存v离farV的距离long farDis = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {long[] cur = queue.poll();int nextV = (int) cur[0];if (graph.containsKey(nextV)) {for (int[] next : graph.get(nextV)) {// 忽略掉第一直径的端点if (next[0] != u && !visited[next[0]]) {// 为了找到离v最远的点，如果找到更远距离了，则更新距离和遇到的点if (next[1] + cur[1] > farDis) {farDis = next[1] + cur[1];farV = next[0];}visited[next[0]] = true;queue.offer(new long[]{next[0], next[1] + cur[1]});}}}}}// 只有其中一个点不是第一直径的时候，才能更新答案if (u != -1) {res = Math.max(res, farDis);}return farV;}// 邻接表建图，value的[0]存的是与key连接的顶点编号，[1]存的是边长private Map<Integer, List<int[]>> buildGraph(int[][] edges) {Map<Integer, List<int[]>> graph = new HashMap<>();for (int[] edge : edges) {graph.putIfAbsent(edge[0], new ArrayList<>());graph.get(edge[0]).add(new int[]{edge[1], edge[2]});graph.putIfAbsent(edge[1], new ArrayList<>());graph.get(edge[1]).add(new int[]{edge[0], edge[2]});}return graph;}
}

时空复杂度$O(n)$，$n$是树的顶点个数。