SCU 4313 把一棵树切成每段K个点 (n%k)剩下的点不管
题目链接：http://cstest.scu.edu.cn/soj/problem.action?id=4313
判断是不是存在拆图得到新连通分支的点个数是K的倍数注意一个点所连的边只能被切一条
#include<stdio.h>#include<string.h>#define N 200001struct node{int f,t,fn,tn,nex;}edge[N];int edgenum, head[N];void addedge(int u, int v){node E={u,v,0,0,head[u]};edge[edgenum] = E;head[u] = edgenum++;}int n,K,m; //n个点 m条边int du[N],dp[N];bool vis[N], use[N];int ans ;void dfs(int x){for(int i=head[x]; i!=-1; i = edge[i].nex){int v = edge[i].t;if(!vis[v]){vis[v] = 1;dfs(v);dp[x] += dp[v];edge[i].tn = dp[v];edge[i].fn = n - edge[i].tn;if(edge[i].tn %K==0 && !use[v] )ans++, use[v] = 1;if(edge[i].fn %K==0 && !use[x] )ans++, use[x] = 1;}}}int main(){int T,i,j;scanf("%d",&T);while(T--){scanf("%d %d",&n,&K);memset(head,-1,sizeof(head)), edgenum = 0;memset(du,0,sizeof(du));m=n-1;while(m--){int u,v;scanf("%d %d",&u,&v);addedge(u,v);addedge(v,u);du[u]++,du[v]++;}memset(vis,0,sizeof(vis));memset(use,0,sizeof(use));for(int i=1;i<=n;i++)dp[i] = 1;ans = 0;for(int i=1;i<=n;i++)if(du[i] == 1){ vis[i]=1, dfs(i); break;}if(ans>= n/K)printf("YES\n");else printf("NO\n");}return 0;}/*24 21 22 33 44 21 21 31 4*/