Luogu P3915 树的分解

题目描述

https://www.luogu.com.cn/problem/P3915

Solution

注意到如果可行的话，方案一定是唯一的

#include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;

int n, k;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn];
void dfs(int u, int fa) {
    f[u] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u); f[u] += f[v];
    }
    if (f[u] == k) f[u] = 0; 
} 

void work() { fill(head, head + maxn, -1); c1 = 0;
    cin >> n >> k; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } dfs(1, 0);
    cout << (!f[1] ? "YES\n" : "NO\n"); 
} 
    

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}