Notice: Undefined index: name in /usr/www/lib/views/home/viewtitle.html on line 188
-阅读程序 第 18 题
#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 外,最大值是( )。

解答部分以后会开放。