E - Path Decomposition of a Tree

思路：

树形dp。
以结点1为根dfs，对于每个以x为根的子树，统计子树包括x在内的结点数量t，以及x的儿子数量cnt（t=0的不计）。
对于每个以x为根的子树，判断：
t>k：无法形成路径。
t=k ：如果cnt>=3： 无法形成路径，否则 令t=0，视为将此子树移除。
t<k：如果cnt>=2：无法形成路径。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int, int>
#define FU(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, a, b) for (int i = (a); i >= (b); --i)
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 5;
int n, k;
vector<int> vis(N);
vector<int> adj[N];

bool flag = 1;
int dfs(int x) {
    vis[x] = 1;
    int t = 1, cnt = 0;
    for (int e : adj[x]) {
        if (vis[e])
            continue;
        int j = dfs(e);
        t += j;
        if (j != 0)
            cnt++;
    }
    if (t > k || cnt >= 3) {
        flag = 0;
    }
    if (t < k && cnt >= 2) {
        flag = 0;
    }
    if (t == k) {
        t = 0; // x为根的子树是一个路径
    }

    return t;
}

signed main() {
    cin.tie(0)->ios::sync_with_stdio(0);
    cin >> n >> k;
    if (k == 1) {
        cout << "Yes\n";
        return 0;
    }
    for (int i = 1; i <= n * k - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vis[1] = 1;
    dfs(1);
    if (flag) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}