https://www.luogu.com.cn/problem/P3915
题意：有一个n个点的树，判断是否能分解成n/k颗树，保证每棵树的节点数为k。
思路：据说这样分解一棵树，分解方法是固定的。树的知识点几乎都是建立在dfs上。从任意一个点作为根节点出发，遍历子节点，不断深搜。把节点数称为贡献，叶子节点往上返回贡献累加到父节点上，如果加上父节点本身后有k节点，那么可以把这个作为一棵子树剪掉，不计算这棵子树对父节点的贡献。如果在途中遇到 儿子节点太多的父节点形成的树，就可以提前返回答案了(剪枝)，因为这棵子树无论如何也无法按要求分解掉。
#include<stdio.h> #include<iostream> #include<algorithm> #include<cstring> #include<math.h> #include<string> #include<map> #include<queue> #include<stack> #include<set> #include<ctime> #define ll long long #define inf 0x3f3f3f3f const double pi=3.1415926; using namespace std; vector<int>a[100086]; int t,n,k; int dfs(int x,int last)///当前点，父节点 { int res=1;///自己是一个节点,看看有没有没有剪掉的子节点贡献给自己顺便返回给父亲 for(int i=0;i<a[x].size();i++) { int next=a[x][i]; if(next==last)///无向图存两边防止死循环 continue; int num=dfs(next,x);///子树的节点树 if(num==-1) return -1; if(num==k) ///不断dfs，只要形成k节点的子树就可以剪掉,不累加计数 continue; if(num>k)/// return -1; res+=num; } return res; } int main(){ scanf("%d",&t); while(t--){ scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) a[i].clear(); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); a[x].push_back(y); a[y].push_back(x); } int ans=dfs(1,1); if(ans==k) printf("YES "); else printf("NO "); } return 0; }
天上不会掉馅饼，努力奋斗才能梦想成真！