算法分析

• 从任意结点开始，找到每个结点且经过该节点向下走的最大长度d1和次大长度d2，则经过该节点的最大长度是d1 + d2

• dfs(u,father)表示找到u点往下走的最大长度d1

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 10010;
    static int M = N * 2;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static int ans = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //找到u点往下走的最大长度
    static int dfs(int u,int father)
    {
        int d1 = 0;//最大值
        int d2 = 0;//次大值
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            int d = dfs(j,u) + w[i];

            if(d > d1) {d2 = d1; d1 = d;}
            else if(d > d2) {d2 = d;}
        }
        ans = Math.max(ans, d1 + d2);
        return d1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        Arrays.fill(h,-1);
        for(int i = 0;i < n - 1;i ++)
        {
            String[] s1 = reader.readLine().split(" ");
            int a = Integer.parseInt(s1[0]);
            int b = Integer.parseInt(s1[1]);
            int c = Integer.parseInt(s1[2]);
            add(a,b,c);
            add(b,a,c);
        }
        dfs(1,-1);
        System.out.println(ans);
    }
}