求助大佬们,第二个点为什么re了,找半天
  • 板块P1395 会议
  • 楼主zzf12345666
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/4/13 22:06
  • 上次更新2023/10/23 18:33:35
查看原帖
求助大佬们,第二个点为什么re了,找半天
879396
zzf12345666楼主2023/4/13 22:06
import java.util.*;
public class Main {
    static int N=50010;
    static int []e=new int[N];
    static int []ne=new int[N];
    static int []h=new int[N];
    static int []dis=new int[N];
    static int []s=new int[N];
    //存放上一个点是从哪里来的
    static int []pre=new int[N];
    static int idx=0;
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n=in.nextInt();
        int temp=n;
        Arrays.fill(h,-1);
        while(n-->1){
            int a=in.nextInt();
            int b=in.nextInt();
            add(a,b);
            add(b,a);
        }
        //找到重心
        pre[1]=-1;
        //solve函数为了计算每个点的点数
        solve(1);
        int index=0;int min=Integer.MAX_VALUE;
        for(int i=1;i<=temp;i++){
             int v=0;
             //枚举所有与i相邻的点j
             for(int j=h[i];j!=-1;j=ne[j]){
                 int y=e[j];
                 if(y!=pre[i]){
                     v=Math.max(v,s[y]);
                 }
                 else {
                     v=Math.max(v,temp-s[i]);
                 }
             }
             if(v<min){
                min=v;
                index=i;
             }
        }
        Arrays.fill(pre,0);
        pre[index]=-1;
        dfs(index);
        long ans=0;
        for(int i=1;i<=temp;i++){
            ans+=dis[i];
        }
        //输出重心和最小距离和
        System.out.println(index+" "+ans);
    }
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static void solve(int u){
        s[u]=1;
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(pre[u]!=j){
                pre[j]=u;
                solve(j);
                s[u]+=s[j];
            }
        }
    }
    static  void dfs(int u){
        for(int i=h[u];i!=-1;i=ne[i]){
            int j=e[i];
            if(j!=pre[u]){
                pre[j]=u;
                dis[j]=dis[u]+1;
                dfs(j);
            }
        }
    }
}

2023/4/13 22:06
加载中...