BZOJ1131: [POI2008]Sta
题意：给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大。
题解：记录每个点的深度，再根据根节点的深度和逐层推导出其他点的深度和。
我用的是BFS
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
int n,cnt,ans;
int head[],next[],to[],fa[],s[];
ll f[],g[],siz[];
queue<int> q;
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
int main()
{
scanf("%d",&n);
memset(head,-,sizeof(head));
int i,a,b,u;
for(i=;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
q.push();
while(!q.empty())
{
u=q.front();
q.pop();
s[++s[]]=u;
siz[u]++;
for(i=head[u];i!=-;i=next[i])
{
if(to[i]!=fa[u])
{
fa[to[i]]=u;
q.push(to[i]);
}
}
}
for(i=n;i>=;i--)
{
siz[fa[s[i]]]+=siz[s[i]];
f[fa[s[i]]]+=siz[s[i]]+f[s[i]]; //f[i]表示i的所有儿子到i的深度之和
}
g[]=f[ans=];
for(i=;i<=n;i++)
{
g[s[i]]=g[fa[s[i]]]+n-(siz[s[i]]<<); //g[i]表示所有点到i的距离之和，可由g[fa[i]]推出
if(g[ans]<g[s[i]]||(g[ans]==g[s[i]]&&ans>s[i]))
ans=s[i];
}
printf("%d",ans);
return ;
}
POJ3107:Godfather
题意：在树中找一个点，使去掉这个点后，剩余的所有子树节点个数的最大值最小，求满足要求的所有节点。
题解：求出每个子树的节点个数size[x]，则答案为min(size[y],n-size[x]),y是x的儿子。
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn=;
int n,cnt,minn;
int head[maxn],to[maxn<<],next[maxn<<],s[maxn],f[maxn],sta[maxn];
int readin()
{
int ret=; char gc;
while(gc<''||gc>'') gc=getchar();
while(gc>=''&&gc<='') ret=ret*+gc-'',gc=getchar();
return ret;
}
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void dfs(int x,int fa)
{
s[x]=;
for(int i=head[x];i!=-;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
s[x]+=s[to[i]];
f[x]=max(f[x],s[to[i]]);
}
}
f[x]=max(f[x],n-s[x]);
minn=min(minn,f[x]);
}
int main()
{
n=readin();
memset(head,-,sizeof(head));
int i,a,b;
for(i=;i<n;i++)
{
a=readin(),b=readin();
add(a,b),add(b,a);
}
minn=<<;
dfs(,);
for(i=;i<=n;i++) if(f[i]==minn) sta[++sta[]]=i;
for(i=;i<sta[];i++) printf("%d ",sta[i]);
printf("%d",sta[sta[]]);
return ;
}
POJ1655:Balancing Act
题意：同POJ3107
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=;
int n,minn,ans,cnt;
int s[maxn],to[maxn<<],next[maxn<<],head[maxn];
int readin()
{
int ret=; char gc;
while(gc<''||gc>'') gc=getchar();
while(gc>=''&&gc<='') ret=ret*+gc-'',gc=getchar();
return ret;
}
void add(int a,int b)
{
to[cnt]=b;
next[cnt]=head[a];
head[a]=cnt++;
}
void dfs(int x,int fa)
{
int t=;
s[x]=;
for(int i=head[x];i!=-;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
s[x]+=s[to[i]];
t=max(t,s[to[i]]);
}
}
t=max(t,n-s[x]);
if(t<minn||(t==minn&&x<ans)) ans=x,minn=t;
}
void work()
{
n=readin();
memset(head,-,sizeof(head));
ans=cnt=,minn=<<;
int i,a,b;
for(i=;i<n;i++)
{
a=readin(),b=readin();
add(a,b),add(b,a);
}
dfs(,);
printf("%d %d\n",ans,minn);
}
int main()
{
int t=readin();
while(t--) work();
return ;
}
BZOJ1827:[Usaco2010 Mar]gather 奶牛大集会
题意：与上一题差不多，只不过不同的点有不同的牛居住，求的是所有牛到核心的最小总路程