记录编号	38455	评测结果	AAAAAAAAAA
题目名称	[SOJ 1140] 国王的遗产	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	0.260 s
提交时间	2012-04-19 13:25:18	内存使用	0.98 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

vector<int>tree[30010];
int pre[30010],num[30010],path[30010],N,K,root,tot,now,pro,ans;
bool vis[30010];

void build(int u,int fa)
{
    pre[u]=fa; 
	path[u]=u; 
	num[u]=1;
    for(int i=0;i<tree[u].size();i++)
    {
        int t=tree[u][i];
        if(!vis[t]&&t!=fa)
        {
            build(t,u);
            path[u]=min(path[u],path[t]);
            num[u]+=num[t];
        }
    }
}

void update(int u)
{
    path[u]=u;
    for(int i=0;i<tree[u].size();i++)
    {
        int t=tree[u][i];
        if(!vis[t])
        {
            update(t);
            path[u]=min(path[u],path[t]);
        }
    }
}

void solve(int u)
{
    int tnum=num[u],tpro=0,sum=tnum<<1;
    if(sum>tot||sum==tot&&path[root]<path[u]) 
	{
		tnum=tot-tnum;
		tpro=1;
	}
    if(ans<tnum)
	{		
		ans=tnum;
		pro=tpro;
		now=u;
	}
    else if(ans==tnum)
    {
        if(pro!=tpro)
		{			
			now=pro?now:u;
			pro=1;
		}
        else if(!pro&&path[u]<path[now]||pro&&u>now) 
			now=u;
    }
    for(int i=0,t;i<tree[u].size();i++)
    {
        t=tree[u][i];
        if(!vis[t]) 
			solve(t);
    }
}

int main()
{
	freopen("legacy.in","r",stdin);
	freopen("legacy.out","w",stdout);
    scanf("%d%d",&N,&K);
    for(int i=1;i<N;i++)
    {
		int a,b;
        scanf("%d%d",&a,&b);
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    root=1;
	tot=N;
    build(root,-1);
    for(int i=2;i<=N;i++)
        tree[i].erase(find(tree[i].begin(),tree[i].end(),pre[i]));
    for(int i=1;i<K;i++)
    {
        ans=0;
        solve(root);
        printf("%d ",ans);
        tot-=ans;
        if(pro) 
		{
			root=now;
			pre[root]=-1;
		}
        else
        {
            vis[now]=true;
            for(int j=num[now];pre[now]!=-1;num[pre[now]]-=j,now=pre[now]);
            update(root);
        }
    }
    printf("%d\n",tot);
    return 0;
}