算法分析

树形dp

• 1、先通过树形dp求出每个点往下走的最大长度和次大长度，并且更新整棵树的最大路径ans

• 2、枚举每一个结点i，设该点的最大长度是d1[i]，次大长度是d2[i]，若d1[i] + d2[i] == ans，表示最大路径是从该点得出的，通过dfs2找到最大长度的路径，dfs3找到次大长度的路径，并对路径的点进行标记

时间复杂度 $O(n)$

Java 代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N = 2 * 100010,M = 2 * N;
    static int n;
    static int[] d1 = new int[N];//记录某个结点往下走的最大长度
    static int[] d2 = new int[N];//记录某个结点往下走的次大长度
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int ans = 0;
    static boolean[] st = new boolean[N];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //返回从该点往下走的最大长度
    static int dfs1(int u,int father)
    {
        int first = 0,second = 0;
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j == father) continue;
            int d = dfs1(j,u) + 1;
            if(d > d1[u])
            {
                d2[u] = d1[u]; second = first;
                d1[u] = d; first = j;

            }
            else if(d > d2[u])
            {
                d2[u] = d; second = j;
            }
        }
        ans = Math.max(ans, d1[u] + d2[u]);
        return d1[u];
    }
    //从该点往下找最大长度
    static void dfs2(int u)
    {
        st[u] = true;
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            //最大值
            if(d1[u] == d1[j] + 1) dfs2(j); 
        }
    }
    //从该点往下找次大长度
    static void dfs3(int u)
    {
        st[u] = true;
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            //次大值
            if(d2[u] == d1[j] + 1) dfs2(j);
        }
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        Arrays.fill(h, -1);
        for(int i = 0;i < n - 1;i ++)
        {
            int a = scan.nextInt();
            int b = scan.nextInt();
            add(a,b);
            add(b,a);
        }
        dfs1(0,-1);
        for(int i = 0;i < n ;i ++) 
        {
            if(d1[i] + d2[i] == ans) 
            {
                dfs2(i);
                dfs3(i);
            }
        }
        for(int i = 0;i < n;i ++) 
        {
            if(st[i]) System.out.println(i);
        }
    }
}