在做树的重心模板,然后输入的时候死循环了,发现是
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
es[x].push_back(y);
es[y].push_back(x);
这里的问题,这样写不对吗
求助/kel
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,p[MAXN],sz[MAXN],f[MAXN],g[MAXN];
//p[i]记录i的父亲,sz[i]记录以i为根的子树大小 f[i]表示儿子为根的最大子树的大小,g[i]是删除i后最大分支的大小
vector < vector <int> > es;
void dfs(int u,int fa){//通过dfs求sz[],p[]
p[u]=fa;//初始化
sz[u]=1;//初始化
for(int i=0;i<es[u].size();i++){
int v=es[u][i]; //找一个与之联通的点(子节点)
if(v==fa) continue; //排除掉v是父亲节点的情况
dfs(v,u);
sz[u]+=sz[v]; //加上子节点的子树数量
}
}
int main()
{
cin>>n;
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
es[x].push_back(y);
es[y].push_back(x);
}
//输入
dfs(1,0);
//求得sz和p
for(int u=1;u<=n;u++){
for(int i=0;i<es[u].size();i++){
int v=es[u][i];
if(v==p[u]) continue; //排除父亲节点的可能
f[u]=max(f[u],sz[v]); //计算u儿子为根的最大子树的的大小
}
}
for(int u=1;u<=n;u++){
g[u]=max(f[u],n-sz[u]);//g[u]由两部分的最大值取得:以u的儿子们形成的区块,u的长辈们组成的区块
}
int id=min_element(g+1,g+1+n)-g;//找到最小的g
cout<<id<<" "<<g[id]<<endl;
return 0;
}