题解 | #图的遍历#

这是一到技巧题， 核心思想就是 从1出发，只有最长路径才不会被重复走两次， 大家可以在纸上模拟几个场景就知道。

那么就是 2（总边数）- 最长路径的边数。 边数为 n-1, n为顶点数， 最后公式演变为 2（n-1）-最长路径边数。

所以现在的首要问题是找最长路径， 采用递归方式找，可以用 visited 标记哪些节点是否走过的，防止走回头路

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            ArrayList[] graph = new ArrayList[a + 1];

            for (int i = 0; i < graph.length; i++) {
                graph[i] = new ArrayList();
            }

            for (int i = 0; i < a - 1; i++) {
                int start = in.nextInt();
                int end = in.nextInt();
                graph[start].add(end);
                graph[end].add(start);
            }

            //a-1  为边数
            int longPath = findLongPath(1, graph, -1, new boolean[a + 1]);

            System.out.println((2 * (a - 1)) - longPath);
        }
    }

    /**
     * 从1 出发,找 最长路径
     * <p>
     * return ,最长路径
     */
    private static int findLongPath(int start, ArrayList[] graph, int curPathLen,
                                    boolean[] visit) {
        if (!visit[start]) {
            visit[start] = true;
            curPathLen++;
            int maxSubLen = 0;
            for (Object o : graph[start]) {
                int end = (int) o;
                //是否已经被访问
                int longPath = findLongPath(end, graph, 0, visit);
                maxSubLen = Math.max(longPath, maxSubLen);

            }
            return curPathLen + maxSubLen;
        } else {
            return 0;
        }
    }
}