小红书4.9笔试

1题选手，太菜了受不了了

1.平衡，给出一个树，删除任意一条边，求删除后两个树的节点之差的绝对值最小值，并且求方案数目

输入：

第一行 节点数目n

第二行连续n-1行，输入两个数，表示两个节点有1条边

输出

最小值 空格 方案数

思路：

一次遍历记录子树节点数目在subtrees。

一次遍历在遍历子节点的时候 算出删除父子节点边后的 两个树的节点数目之差，借助subtrees，同时得到最小值。

一次遍历 同上次遍历，但是是判断节点数目之差等于最小值的情况数目。

import java.util.*;

public class Main {
    static int n;
    static int mins=Integer.MAX_VALUE;
    static int[] subtrees;
    static boolean[] visit;
    static boolean[] visit2;
    static boolean[] visit3;
    static ArrayList<Integer>[] res;
    static  int result=0;

    public static int dfs1(int i){
        visit[i] = true;
        int subcount=1;
        for(int j=0;j<res[i].size();j++){
            int next = res[i].get(j);
            if(!visit[next]){
                subcount += dfs1(next);
            }
        }
        subtrees[i]=subcount;
        return subcount;
    }

    public static void dfs2(int i){
        visit2[i]=true;
        for(int j=0;j<res[i].size();j++){
            int next = res[i].get(j);
            int ret = subtrees[next];
            int ret2 = n-ret;
            int chec = Math.abs(ret2-ret);
            if(mins>chec)mins=chec;
            if(!visit2[next]){
                dfs2(next);
            }
        }
    }

    public static void dfs3(int i){
        visit3[i] = true;
        for(int j=0;j<res[i].size();j++){
            int next = res[i].get(j);
            if(!visit3[next]){
                int ret = subtrees[next];
                int ret2 = n-ret;
                int chec = Math.abs(ret2-ret);
                if(mins==chec)result++;
                dfs3(next);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        res = new ArrayList[n+5];
        visit = new boolean[n+5];
        visit2 = new boolean[n+5];
        visit3 = new boolean[n+5];
        subtrees = new int[n+5];
        for(int i=0;i<n+5;i++){
            res[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<n-1;i++){
            int v = sc.nextInt();
            int u = sc.nextInt();
            res[v].add(u);
            res[u].add(v);
        }
        dfs1(1);
        dfs2(1);
        dfs3(1);
        System.out.print(mins);
        System.out.print(" ");
        System.out.println(result);
    }
}