题意：求出树重心的编号（如果有多个重心则取编号最小的那个），以及以重心为根子树大小的最小值
分析：求重心裸题，其实就是找到一个点作为根，使各子树大小size的最大值最小。dfs即可求解。
技能： t=max(t,n-size[u]); 注意这句话不能漏，可以理解比较形象地为子树不一定在下面，还可能在上面。
代码：
#include<cstdio> #include<cstring> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;++i) #define dep(i,j,k) for (int i=j;i>=k;--i) #define to e[i].v #define Cl(a) memset(a,0,sizeof(a)) #define inf 1234567890 #define max(a,b) a>b? a:b #define N 20010 struct node{ int v,next; }e[N*2]; int head[N],size[N],id,n,ans,s; int read() { int f=1,x=0;char ch=getchar(); for (;ch>'9'||ch<'0';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; return x*f; } void add(int u,int v) {e[id].v=v; e[id].next=head[u]; head[u]=id++;} void dfs(int u,int lastfa) { size[u]=1; int t=0; for (int i=head[u];i;i=e[i].next) if (to^lastfa) { dfs(to,u); size[u]+=size[to]; t=max(t,size[to]); } t=max(t,n-size[u]); if (t<s||t==s && u<ans) { ans=u; s=t; } } int main() { int t=read(); for (;t--;) { n=read(); id=1; Cl(head); Cl(size); rep(i,1,n-1) {int u=read(),v=read(); add(u,v); add(v,u);} ans=inf; s=inf; dfs(1,1); printf("%d %d\n",ans,s); } return 0; }
