#include <iostream>
using namespace std;
const int inf =0x3f3f3f3,N=4e5+5;
struct edge {
int to,nt ;
}E[N<<1];
int cnt, n,m,rt,MX;
int H[N],sz[N],mxs[N];
void add_edge(int u, int v) {
E[++cnt]=(edge) {v,H[u]};
H[u]=cnt;
}
void dfs(int u, int fa) {
sz[u]=1;
for (int e=H[u]; e; e=E[e].nt) {
int v=E[e].to;
if (v==fa) continue;
dfs(v,u);
sz[u]+=sz[v];
mxs[u]=max(mxs[u],sz[v]);
}
mxs[u] =max(mxs[u],n-sz[u]);
if (mxs[u]<mxs[rt])rt=u;
if (mxs[u]==mxs[rt] &&u<rt)rt=u;
}
int main() {
cin>>n,
rt =cnt= 0;
for (int i=1; i<=n; i++) {
int u,v;
cin>>u>>v;
add_edge(u,v);
add_edge(v,u);
}
mxs[0] = inf ;
dfs(1,0);
cout<<rt<<' '<<mxs[rt]<<'\n';
return 0;
}
判断题
1) 第33,34行只需保留任意一行也不会影响程序的正确性。()
2) 第37行函数调用dfs(x,y)，只需保证1≤x≤n,y≤0即可。()
3) 第32行输入若有重复(重边)，不影响输出结果的正确性。()
4) 程序运行结束时可能存在正整数i(i≤n)使sz[i]等于mxs[i]。()
选择题
5) n=6,二元组(u,v)各个值分别是{(1，3),(6.3),(2,6),(5,6),(3,4)},则输出是()。
6) 若n=1000，则程序运行后mxs[]数组中除初始值 inf 外，最大值是( )。