学步园

//搜索，暴力<br /> //这题卡了我几天，检查到最后，居然是我的minID维护错误！我艹！这种错误居然卡了我几天！！！我就是一个超级无敌大水人！<br /> //不过卡了这几天也好，程序也经过不断优化<br /> //做法是预处理出以每个结点为根的子树有多少个结点cnt，以每个结点为根的子树最小编号minID<br /> //接着枚举所有边，暴力找出每个可行方案<br /> //在搜寻每一个可行方案，都以编号最小的结点作为根，这一个优化方案，可以省去搜索比较上下两部分的最小编号值<br /> //这题有几个重要结论是需要证明的<br /> //1、在树中仅存在一条边能将一棵树均分成数目相等的两棵树<br /> //2、在树中不存在两条边能将一棵树划分成X个(X<N/2)结点且包含根结点<br /> #include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> using namespace std;<br /> const int MAX = 30005;<br /> int N,K;<br /> int head[MAX],next[MAX*2],V[MAX*2],edge;<br /> int prt[MAX],cnt[MAX],minID[MAX],ans[MAX];<br /> bool del[MAX],vis[MAX];<br /> void addEdge(int u,int v)<br /> {<br /> V[edge] = v;<br /> next[edge] = head[u];<br /> head[u] = edge++;<br /> }<br /> void init(int x,int fa)//预处理以x为根的情况<br /> {<br /> cnt[x] = 1;<br /> prt[x] = fa;<br /> minID[x] = x;<br /> for(int e = head[x];e != -1;e = next[e])<br /> {<br /> int y = V[e];<br /> if(fa == y || del[y]) continue;<br /> init(y,x);<br /> cnt[x] += cnt[y];<br /> minID[x] = min(minID[x],minID[y]);//之前这里写成min(x,minID[y])，WA了一天<br /> }<br /> }<br /> void dfs(int x,int fa,int flag)<br /> {<br /> del[x] = 1;<br /> for(int e = head[x];e != -1;e = next[e])<br /> {<br /> int y = V[e];<br /> if(fa == y || del[y] || y == flag) continue;<br /> dfs(y,x,flag);<br /> }<br /> }<br /> void solve()<br /> {<br /> int flag,_max,_min;<br /> for(int i = 1;i < K;++i)<br /> {<br /> int root = 1;<br /> while(del[root]) root++;//每次都取编号值最小的结点为根<br /> init(root,0);<br /> _max = 0;<br /> _min = MAX;<br /> for(int i = 1;i <= N;++i)<br /> {<br /> if(i == root ||del[i]) continue;<br /> int t1 = cnt[root] - cnt[i];//t1是包含根的部分<br /> int t2 = cnt[i];//t2是以i为根的子树部分<br /> if(t1 == t2)//用结论一，可以立即得到答案，只会有一条边满足这种情况<br /> {<br /> _max = t1;<br /> flag = i;<br /> _min = minID[root];<br /> break;<br /> }<br /> if(t1 > _max && t1*2 <= cnt[root])<br /> {<br /> flag = i;<br /> _max = t1;<br /> _min = minID[root];<br /> }<br /> if(t2 >= _max && t2*2 <= cnt[root])<br /> {<br /> if(t2 == _max && minID[i] < _min)<br /> {<br /> _max = t2;<br /> flag = i;<br /> _min = minID[i];<br /> }<br /> else if(t2 > _max)<br /> {<br /> _max = t2;<br /> flag = i;<br /> _min = minID[i];<br /> }<br /> }<br /> }<br /> if(cnt[flag] >= cnt[root] - cnt[flag])<br /> {<br /> ans[i] = cnt[root] - cnt[flag];<br /> dfs(root,0,flag);<br /> }<br /> else<br /> {<br /> ans[i] = cnt[flag];<br /> dfs(flag,prt[flag],prt[flag]);<br /> }<br /> }<br /> ans[K] = N;<br /> for(int i = 1;i < K;++i)<br /> {<br /> printf("%d ",ans[i]);<br /> ans[K] -= ans[i];<br /> }<br /> printf("%d/n",ans[K]);<br /> }<br /> int main()<br /> {<br /> // freopen("in.txt","r",stdin);<br /> int u,v;<br /> memset(head,-1,sizeof(head));<br /> scanf("%d%d",&N,&K);<br /> for(int i = 1;i < N;++i)<br /> {<br /> scanf("%d%d",&u,&v);<br /> addEdge(u,v);<br /> addEdge(v,u);<br /> }<br /> solve();<br /> }