洛谷P3915 树的分解 题解

题目链接：P3915 树的分解

题意：

给出 $N$ 个点的树和 $K$，问能否把树划分成 $\frac{N}{K}$ 个连通块，且每个连通块的点数都是 $K$。

输入格式：

第一行，一个整数 $T$，表示数据组数。接下来 $T$ 组数据，对于每组数据：

第一行，两个整数 $N, K$。

接下来 $N - 1$ 行，每行两个整数 $A_i, B_i$，表示边 $(A_i, B_i)$。点用 $1, 2, \ldots, N$ 编号。

输出格式：

对于每组数据，输出 YES 或 NO。

数据范围：

对于 $100 \%$ 的数据，$1 \le T \le 10$，$1 \le N ,K \le 10^5$。

贪心好题。

首先 $n \bmod k \ne 0$ 肯定无解。

考虑从下往上依次考虑每个点

如果它的 $\mathtt{sz}_u = k$ 那就把它的砍掉，并令 $\mathtt{sz}_u \gets 0$

在有解的情况下，这么做一定可以分出来。

如果某个 $\mathtt{sz}_u > k$ 怎么办呢？ 可以发现此时一定无解，根据归纳法可证。

因为此时如果强行切出一个 $k$ 的块，则 $u$ 至少有一个儿子 $v$ 无法被切割。

时间复杂度 $\mathcal{O}(Qn)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(1e5+15))

int n,k,ans,sz[N];
vector<int> g[N];
void dfs(int u,int f)
{
    sz[u] = 1;
    for(int v : g[u])
    {
        if(v == f) continue;
        dfs(v,u); sz[u] += sz[v];
    }
    if(sz[u] == k) ++ans, sz[u] = 0;
}
void solve()
{
    read(n); read(k); ans = 0;
    for(int i=1; i<=n; i++) { sz[i] = 0; g[i].clear(); }
    for(int i=1,u,v; i<n; i++)
    {
        read(u); read(v);
        g[u].push_back(v); g[v].push_back(u);
    }
    if(n % k != 0) return  puts("NO"),void(0); 
    dfs(1,1); puts(((ans == n/k) ? ("YES") : ("NO")));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; read(Q); while(Q--) solve();
    return 0;
}