美团笔试第一题

import java.util.Scanner;

public class Meituan1 {
    static int N;
    static int[][] mat;
    static boolean[] flag; //标记节点是否已访问过

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        mat = new int[N][N];
        int n = N;
        while (n-- > 1) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            mat[i - 1][j - 1] = mat[j - 1][i - 1] = 1;
        }
        flag = new boolean[N];
        int maxDepth = depth(0);
        flag = new boolean[N];
        System.out.println(dfs(0) - maxDepth);
        sc.close();
    }
    
     //递归求解访问所有子树并返回的路径总和
    static int dfs(int start) {
        flag[start] = true;
        int res = 0;
        for (int i = 0; i < N; i++) {
            if (i != start && mat[start][i] != 0 && !flag[i]) {
                res += 2 + dfs(i);
            }
        }
        return res;
    }
    
     //递归求解树的高度
    static int depth(int start) {
        flag[start] = true;
        int res = 0;
        for (int i = 0; i < N; i++) {
            if (i != start && mat[start][i] != 0 && !flag[i]) {
                int idepth = 1 + depth(i);
                if (idepth > res) res = idepth;
            }
        }
        return res;
    }
}

	



	然而只过了9%。。。求大佬指正。。