关于树的重心：百度百科
有关博客：http://blog.csdn.net/acdreamers/article/details/16905653
1.Balancing Act
题目大意：
有t组数据。每组数据给出n个点和n-1条边，构成一棵树，求该树的重心及删掉该点后形成的每棵子树的节点数。
代码：
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=; int n,cnt,H[N<<],Ans,size,son[N];
bool vis[N];
struct Edge
{
int to,nxt;
}e[N<<]; void read(int &now)
{
now=;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))now=(now<<)+(now<<)+c-'',c=getchar();
} void AddEdge(int u,int v)
{
e[++cnt].to = v;
e[cnt].nxt = H[u];
H[u] = cnt;
} void Init()
{
Ans=size=0x7fffffff;
for(int i=;i<=n;++i)
vis[i]=son[i]=H[i]=;
cnt=;
read(n);
int a,b;
for(int i=;i<n;++i)
read(a),read(b),AddEdge(a,b),AddEdge(b,a);
} void DFS(int cur)
{
vis[cur]=;
son[cur]=;
int tmp=;
for(int i=H[cur];i;i=e[i].nxt)
{
int to=e[i].to;
if(!vis[to])
{
DFS(to);
son[cur]+=son[to]+;
tmp=max(tmp,son[to]+);
}
}
tmp=max(tmp,n-son[cur]-);
if(size>tmp ||size==tmp&&Ans>cur)
{
Ans=cur;
size=tmp;
}
} int main()
{
int t;
read(t);
while(t--)
{
Init();
DFS();
printf("%d %d\n",Ans,size);
}
return ;
}
Balancing Act
2.Godfather
题目大意：
按升序输出该树的重心。
代码：
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=; int n,cnt,tot,size,H[N<<],Ans[N],son[N];
bool vis[N];
struct Edge
{
int to,nxt;
}e[N<<]; void read(int &now)
{
now=;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))now=(now<<)+(now<<)+c-'',c=getchar();
} void AddEdge(int u,int v)
{
e[++cnt].to = v;
e[cnt].nxt = H[u];
H[u] = cnt;
} void Init()
{
memset(H,,sizeof H);
memset(vis,,sizeof vis);
memset(Ans,0x3f,sizeof Ans);
size=0x7fffffff;
cnt=tot=;
read(n);
int x,y;
for(int i=;i<n;++i)
read(x),read(y),AddEdge(x,y),AddEdge(y,x);
} void DFS(int cur)
{
vis[cur]=;
son[cur]=;
int tmp=;
for(int i=H[cur];i;i=e[i].nxt)
{
int to=e[i].to;
if(!vis[to])
{
DFS(to);
son[cur]+=son[to]+;
tmp=max(tmp,son[to]+);
}
}
tmp=max(tmp,n-son[cur]-);
if(size>tmp)
{
size=tmp;
tot=;
Ans[tot]=cur;
}
else if(size==tmp)
{
Ans[++tot]=cur;
}
} int main()
{
Init();
DFS();
sort(Ans+,Ans++tot);
for(int i=;i<=tot;++i)
printf("%d ",Ans[i]);
return ;
}
Godfather