SCU 4313 把一棵树切成每段K个点 (n%k)剩下的点不管

题目链接：http://cstest.scu.edu.cn/soj/problem.action?id=4313

判断是不是存在拆图得到新连通分支的点个数是K的倍数
注意一个点所连的边只能被切一条

#include<stdio.h>

#include<string.h>

#define N 200001

struct 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;

}

/*

2

4 2

1 2

2 3

3 4

4 2

1 2

1 3

1 4

*/

SCU 4313 把一棵树切成每段K个点 (n%k)剩下的点不管的相关教程结束。