ZOJ - 4045District Division
题目大意：给你n个节点的树，然后让你划分这棵数使得，每一块都恰好k个节点并且两两间是连通的，也就是划分成n/k个连通集，如果可以输出YES，并输出对应的划分，否则输出NO
一开始觉得是树形dp，但不知道如何下手，看大佬的做法才恍然大悟，其实就是找子树大小刚好是k的节点，刚让它作为这一分块的根节点，它的父节点就不再记录它的子树大小，详情见代码
#include<cstdio>
#include<vector>
using namespace std;
const int N=;
struct Side{
int v,ne;
}S[*N];
vector<int> ans;
int n,k,is,m,sn;
int head[N],size[N],book[N];
void add(int u,int v)
{
S[sn].v=v;
S[sn].ne=head[u];
head[u]=sn++;
}
void fp(int u,int f)
{
for(int i=head[u];i!=-;i=S[i].ne)
if(S[i].v!=f&&!book[S[i].v])
{
book[S[i].v]=u;
printf(" %d",S[i].v);
fp(S[i].v,u);
}
}
int dfs(int u,int f)
{
if(!is)
return ;
size[u]=;
for(int i=head[u];i!=-;i=S[i].ne)
{
if(S[i].v!=f&&!book[S[i].v])
dfs(S[i].v,u);
if(S[i].v!=f&&!book[S[i].v])//如果它的这个子节点没有作为划分的子树的根节点
size[u]+=size[S[i].v];//那么统计上它的大小
}
if(size[u]>k)//如果它的子树大小大于k那么它分出一个大小k的子树后
return is=;//剩下的会不足k个
if(size[u]==k)
{
ans.push_back(u);//保存作为划分的子树根节点的节点
book[u]=f;//并保存它的父节点，不然在输出时会PE
}
return ;
}
int main()
{
int t,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
ans.clear();
for(int i=;i<=n;i++)
book[i]=,head[i]=-;
sn=;
for(int i=;i<n-;i++)
{
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
is=;
if(dfs(,-))
{
printf("YES\n");
for(int i=;i<ans.size();i++)
{
printf("%d",ans[i]);
fp(ans[i],book[ans[i]]);
printf("\n");
}
}
else
printf("NO\n");
}
return ;
}
多想一想