【题解】HackerRank-Cut Tree

Posted on Edited on In Disqus:

题目

https://www.hackerrank.com/challenges/cuttree/problem

题意

求树 T 的子树（联通块） T' 的个数 ，满足 T 与 T - T' 之间至多有 K 条边相连。

题解

  • 树形 dp
  • \(f[u][k]\) 表示结点 \(u\) 为根的子树 T 中以 \(u\) 为根的 T' 个数，满足 T 与 T - T' 之间至多有 k 条边相连。
  • 把一个儿子 \(v\) 纳入考虑的时候，选择 \(v\) 的话就做一次背包，不选的话会增加一条相邻的边。
  • 最后枚举 T' 的 LCA，如果不是根的话要额外多一条连向 LCA 的父亲。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 50 + 5;
vector<int> G[N];
LL f[N][2 * N];
LL t[2 * N];

void go(int u, int fa) {
    f[u][0] = 1;
    for (int& v: G[u]) {
        if (v == fa) continue;
        go(v, u);
        copy(f[u], f[u] + N, t);
        FORD (i, N - 1, -1)
            FOR (j, 0, i + 1)
                f[u][i] += f[v][j] * f[u][i - j];
        FOR (i, 0, N) f[u][i] -= t[i];
        FOR (i, 0, N) f[u][i + 1] += t[i];
    }
}

int main() {
    int n, k; cin >> n >> k;
    FOR (_, 1, n) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].push_back(v); G[v].push_back(u);
    }
    go(1, -1);
    LL ans = 0;
    FOR (i, 1, n + 1)
        FOR (j, 0, k + 1)
        ans += f[i][j - (i != 1)];
    cout << ans + 1 << endl;
}