DDOSvoid's Blog

Luogu P4516 [JSOI2018]潜入行动

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

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

简要题意：给定一棵 $n$ 个点的无根树，现在有 $k$ 个监听装置，每个节点至多安放一个监听装置，一个安放了监听装置的节点可以监听相邻的节点，但不能监听自己，求恰好使用 $k$ 个监听装置且每个节点都至少被一个节点监听的方案数

$n\le 10^5,k\le 100$

Solution

我们令 $f[u][S][0/1][0/1]$ 表示 $u$ 的子树内一共使用了 $S$ 个监听装置，$u$ 点是否使用监听装置，$u$​ 点是否被监听到

时间复杂度 $O(nk)$

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
49
50
51
52
53
54
55
56
#include <iostream>
#define maxn 100010
#define maxm 110
using namespace std;

const int p = 1000000007;

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

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][maxm][2][2], g[maxm][2][2], sz[maxn];
void dfs(int u, int fa) {
    sz[u] = 1; f[u][0][0][0] = f[u][1][1][0] = 1; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u);
        for (int s = 0; s <= min(k, sz[u] + sz[v]); ++s)
            for (int o1 = 0; o1 < 2; ++o1)
                for (int o2 = 0; o2 < 2; ++o2) g[s][o1][o2] = 0;
        for (int s = 0; s <= min(k, sz[u]); ++s)
            for (int t = 0; t <= min(k, sz[v]) && s + t <= k; ++t)
                for (int p1 = 0; p1 < 2; ++p1)
                    for (int p2 = 0; p2 < 2; ++p2)
                        for (int q1 = 0; q1 < 2; ++q1)
                            for (int q2 = 0; q2 < 2; ++q2)
                                if (p1 | q2)
                                    g[s + t][p1][p2 | q1] = add(g[s + t][p1][p2 | q1],
                                                                1ll * f[u][s][p1][p2] * f[v][t][q1][q2] % p);
        sz[u] += sz[v];
        for (int s = 0; s <= min(k, sz[u]); ++s)
            for (int o1 = 0; o1 < 2; ++o1)
                for (int o2 = 0; o2 < 2; ++o2) f[u][s][o1][o2] = g[s][o1][o2];
    }
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    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 << add(f[1][k][0][1], f[1][k][1][1]) << "\n";
    return 0;
}