题解 P3915 【树的分解】
大致分四步:
- 根据给出的边将图建好(树)
- 求出每个节点的f[i](即以该节点为树根的子树大小)
- 当一个节点的f[i]==k时,即以该节点为树根的子树可当成一个连通块。所以f[i]=0,cnt++
- 多组数据要清零
具体操作见代码:
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int f[maxn],n,T,x,y,lnk[maxn],nxt[maxn<<1],son[maxn<<1],tot,k,cnt;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
inline void Dfs(int x,int fa){
f[x]=1;
for (int i=lnk[x];i;i=nxt[i])
if (son[i]!=fa){
Dfs(son[i],x);
f[x]+=f[son[i]];
}
if (f[x]==k) f[x]=0,cnt++;
}
int main(){
T=read();
while (T--){
n=read(),k=read();
memset(lnk,0,sizeof lnk);cnt=0,tot=0;
memset(f,0,sizeof f);
for (int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
if (n%k){printf("NO\n");continue;}
Dfs(1,0);
if (cnt==n/k) printf("YES\n");
else printf("NO\n");
}
return 0;
}