洛谷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;
}