为啥样例都过不了
  • 板块P1395 会议
  • 楼主better_Z
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/28 22:33
  • 上次更新2023/11/2 17:25:49
查看原帖
为啥样例都过不了
865793
better_Z楼主2023/9/28 22:33
#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e4+10;
int f[maxn],len[maxn],size[maxn],n,center,sum=0;
vector<int>q[maxn];
queue<int>p;
void getcenter(int u,int fa){
    size[u]=1;f[u]=0;
    for(int i=0,j=q[u].size();i<j;i++){
        int v=q[u][i];
        if(v==fa)continue;
        getcenter(v,u);
        size[u]+=size[v];
        f[u]=max(f[u],size[v]);
    }
    f[u]=max(f[u],n-size[u]);
    if(f[u]<f[center]||(f[u]==f[center]&&u<center)){center=u;}
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        q[a].push_back(b);
        q[b].push_back(a);
    }
    center=0;
    f[0]=INT_MAX;
    getcenter(1,0);
    p.push(center);
    while(!p.empty()){
        int next=p.front();p.pop();
        for(int i=0,j=q[next].size();i<j;i++){
            int to=q[next][i];
            if(len[to]||to==next)continue;
            len[to]=len[next]+1;
            sum+=len[to];
            p.push(to);
        }
    }
    cout<<center<<' '<<sum;
    return 0;
}
2023/9/28 22:33
加载中...