原题呈现

森林基站#

题目描述#

熊大为了保卫狗熊岭，要在森林里建立一个由 $n$ 个通信基站组成的预警网络．这 $n$ 个基站由 $n-1$ 条隐蔽的光缆连接，形成了一棵树的结构．

为了保证信号畅通，熊大需要为每个基站分配一个运行频率．频率可以选择 $1 \sim m$ 之间的任意整数．

然而，频率 $k$ 是一个“高功率特殊频率”．由于高功率频率之间会互相干扰，且对周围低功率设备有压制作用，光头强的探测器很容易发现异常．为了安全，熊大设定了以下规则：

整个网络中，最多只能有 $x$ 个基站被分配为频率 $k$ ．
如果某个基站被分配了频率 $k$ ，那么与它通过光缆直接相连的所有相邻基站的频率必须严格小于 $k$ ．

熊大想知道，一共有多少种合法的频率分配方案？两种方案被认为是不同的，当且仅当至少有一个基站被分配了不同的频率．

由于答案可能很大，请将结果对 $998244353$ 取模后告诉熊大．

输入格式#

输入文件名为 forest.in．

输入的第一行包含一个整数 $T$ ，表示测试数据的组数．

对于每组测试数据：

第一行包含四个整数 $n, m, k, x$ ，分别表示基站的数量、可选频率的上限、高功率特殊频率的值，以及最多允许分配频率 $k$ 的基站数量．
接下来 $n-1$ 行，每行包含两个整数 $u, v$ ，表示基站 $u$ 和基站 $v$ 之间有一条光缆相连．

输出格式#

输出文件名为 forest.out．

对于每组测试数据，输出一行一个整数，表示合法的频率分配方案数对 $998244353$ 取模后的结果．

样例#

输入 #1#

输出 #1#

样例解释#

【样例 1 解释】

第 1 组测试数据：有 $3$ 个基站，频率可以选择 $1, 2, 3$ ．高功率特殊频率是 $2$ ，最多允许有 $1$ 个基站使用频率 $2$ ．

不使用频率 $2$ ：每个基站都可以选择频率 $1$ 或 $3$ ，共有 $2^3 = 8$ 种方案．
恰好有 $1$ $1$ 个基站使用频率 $2$ $2$ ：
- 若基站 $1$ 频率为 $2$ ，则相邻的基站 $2$ 频率必须严格小于 $2$ （只能为 $1$ ），基站 $3$ 的频率可以是 $1$ 或 $3$ ，共 $2$ 种方案．
- 若基站 $2$ 频率为 $2$ ，则相邻的基站 $1$ 和 $3$ 频率都必须为 $1$ ，共 $1$ 种方案．
- 若基站 $3$ 频率为 $2$ ，则相邻的基站 $2$ 频率必须为 $1$ ，基站 $1$ 的频率可以是 $1$ 或 $3$ ，共 $2$ 种方案．

合计共有 $8+2+1+2 = 13$ 种合法的分配方案．

第 2 组测试数据：有 $4$ 个基站，结构为以 $1$ 为中心的菊花图．频率可选 $1,2,3$ ，特殊频率是 $2$ ，最多允许 $2$ 个基站使用频率 $2$ ．

若基站 $1$ 使用频率 $2$ ，则基站 $2,3,4$ 必须全部使用频率 $1$ ．共 $1$ 种方案．
若基站 $1$ $1$ 不使用频率 $2$ $2$ ：
- 若基站 $1$ 使用频率 $1$ ，则基站 $2,3,4$ 可随意选择 $1,2,3$ ，但频率 $2$ 的基站数不能超过 $2$ ．这部分共有 $2^3 + 3 \times 2^2 + 3 \times 2 = 8 + 12 + 6 = 26$ 种方案．
- 若基站 $1$ 使用频率 $3$ ，则基站 $2,3,4$ 不能使用频率 $2$ （因为使用频率 $2$ 的基站，其所有邻居的频率必须严格小于 $2$ ）．所以基站 $2,3,4$ 只能选择频率 $1$ 或 $3$ ，共 $2^3 = 8$ 种方案．

总计 $1 + 26 + 8 = 35$ 种方案．

数据范围#

对于所有测试数据，保证：

$1 \le T \le 10$
$1 \le n \le 3000$
$1 \le x \le 3000$
$1 \le k \le m \le 10^9$
$1 \le u, v \le n$
所有测试数据的 $n$ 之和不超过 $10000$ ．

测试点编号	$n \le$	$m \le$	$x \le$	特殊性质
1 ~ 2	10	3	10	无
3 ~ 4	12	$10^9$	12	无
5	15	$10^9$	15	无
6 ~ 8	200	$10^9$	200	无
9 ~ 11	3000	$10^9$	10	无
12 ~ 14	3000	$10^9$	3000	A（菊花图）
15 ~ 17	3000	$10^9$	3000	B（链）
18 ~ 20	3000	$10^9$	3000	无

特殊性质说明：

A：树的形态为菊花图，即存在一个基站 $c$ ，其余所有基站都与基站 $c$ 直接相连．
B：树的形态为一条链，即每个基站的度数均不超过 $2$ ．

观察到 $n\leq 3000$ ，可以支持 $O(n^2)$ 的做法．此题选用 dp．由于每一个节点的决策都只与总共存在的高功率节点和其相邻节点有关，因此，定义 dp[i][j][k] 表示考虑 $i$ 为根的子树，子树内已经有了 $j$ 个高功率节点（包括点 $i$ ），由于根据不同情况， $i$ 也会有不同的取值，因此最后一维 $k\in[0,2]$ ，表示节点 $i$ 频率 $v$ 的取值范围所拥有的方案数：

$1\leq v\leq k-1$ ，此时 $k=0$ ．
$v=k$ ，此时 $k=1$ ．
$k+1\leq v\leq m$ ，此时 $k=2$ ．

不难发现初始状态：考虑了 0 个节点，子树已有 0 个高功率节点，共有 1 种情况．根据树形背包的相关知识，即 g[0][0][0/1/2] = 1．

接下来根据 $k$ 的不同分别考虑转移：

若 $k=0$ ，则表示相邻节点无限制．因此，可以从其子节点 $k\in\{0,1,2\}$ 的状态转移而来．具体来说，若 $v$ 是第 $i$ 个子节点： $g[i][j+k][0] =g[i-1][j][0] \times (\sum_{l=0}^{2}dp[v][k][l])$ ．注意其中是加号还是乘号．互斥的状态是相加，承接的状态是相乘．
若 $k=1$ ，则其相邻节点只能取到 $[1,k)$ ．因此，可以从其子节点 $k=0$ 的状态转移而来．具体来说，若 $v$ 是第 $i$ 个子节点： $g[i][j+k][1] =g[i-1][j][1] \times dp[v][k][0]$ ．
若 $k=2$ ，其相邻节点不能是高功率节点．因此，可以从其子节点 $k\in\{0,2\}$ 的状态转移而来．具体来说，若 $v$ 是第 $i$ 个子节点： $g[i][j+k][2] =g[i-1][j][2] \times (dp[v][k][0] + dp[v][k][2])$ ．

接下来就完全是树形背包的转移．

最终状态是 $\sum_{k=0}^{2}dp[root][x][i]$ ．

小技巧：状态的定义与转移

状态的定义常和问题有关．极简单的状态定义就是根据问题定义状态．例如本题询问有多少种方案数，于是就可以定义 dp 状态为考虑到某个节点（或考虑完某节点的子树）时可行的方案数．

稍复杂的 dp 需要加一些限制条件．如此题，由于一个节点的决策只与其子节点决策和剩余“高功率节点”配额相关，于是需要在状态中增加两维．又由于父节点决策只与子节点决策的范围（与 $k$ 的大小关系）有关，因此可以坍缩一维大小为 3 的维度，使其成为常数维．需要注意的是，

在增加限制时，不得依赖于当前节点的父节点．如，我定义一维状态表示当前节点有没有受到父节点的影响，这是不可行的
状态不能重复、不能遗漏．如，我定义一维常数维，其中 0 表示当前节点不受影响的方案数（当前节点可以取 $[1,m]$ ），1 表示当前节点受影响的方案数（当前状态可以取 $[1,k-1]$ ），这两者在 $[1,k-1]$ 的值域内重叠了．

此外，在转移时，特别是方案数，需要注意运算符号究竟是加号还是乘号．相互排斥的状态需要相加，相互承接的状态需要相乘．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const int N = 3005;
5
const int MOD = 998244353;
6
int n, m, k, x, root;
7
vector<int> e[N];
8
int dp[N][N][3], g[2][N][3], sz[N];
9
void dfs(int u, int fa) {
10
    sz[u] = 1;
11
    for (int i = 0; i < e[u].size(); i++) {
12
        int v = e[u][i];
13
        if (v != fa) {
14
            dfs(v, u);
15
            sz[u] += sz[v];
16
        }
17
    }
18
    if (u != root && e[u].size() == 1) {
19
        dp[u][0][0] = k - 1;
20
        dp[u][1][1] = 1;
21
        dp[u][0][2] = m - k;
22
        return;
23
    }
24
    g[0][0][0] = 1;
25
    g[0][0][1] = 1;
26
    g[0][0][2] = 1;
27
    int totsz = 0;
28
    int offset = 0;
29
    for (int xi = 1; xi <= e[u].size(); xi++) {
30
        int v = e[u][xi - 1];
31
        if (v == fa) {
32
            offset++;
33
            continue;
34
        }
35
        int i = xi - offset;
36
        int now = i & 1, prev = (i + 1) & 1;
37
        memset(g[now], 0, sizeof(g[now]));
38
        for (int j = 0; j <= totsz; j++) {
39
            for (int k = 0; k <= sz[v]; k++) {
40
                (g[now][j + k][0] +=
41
                 1ll * g[prev][j][0] *
42
                 (0ll + dp[v][k][0] + dp[v][k][1] + dp[v][k][2] % MOD) % MOD) %=
43
                    MOD;
44
                (g[now][j + k][1] += 1ll * g[prev][j][1] * dp[v][k][0] % MOD) %=
45
                    MOD;
46
                (g[now][j + k][2] += 1ll * g[prev][j][2] *
47
                                     (0ll + dp[v][k][0] + dp[v][k][2] % MOD) %
48
                                     MOD) %= MOD;
49
            }
50
        }
51
        totsz += sz[v];
52
    }
53
    int maxs = (e[u].size() - offset) & 1;
54
    for (int i = 0; i <= totsz; i++) {
55
        (dp[u][i][0] = 1ll * g[maxs][i][0] * (k - 1) % MOD) %= MOD;
56
        dp[u][i + 1][1] = g[maxs][i][1] % MOD;
57
        dp[u][i][2] = 1ll * g[maxs][i][2] * (m - k) % MOD;
58
    }
59
}
60

61
void solve() {
62
    memset(sz, 0, sizeof(sz));
63
    memset(dp, 0, sizeof(dp));
64
    cin >> n >> m >> k >> x;
65
    for (int i = 1; i <= n; i++) {
66
        e[i].clear();
67
    }
68
    root = -1;
69
    for (int i = 1; i < n; i++) {
70
        int u, v;
71
        cin >> u >> v;
72
        if (root == -1) {
73
            root = u;
74
        }
75
        e[u].push_back(v);
76
        e[v].push_back(u);
77
    }
78
    dfs(root, 0);
79
    ll ans = 0;
80
    for (int i = 0; i <= x; i++) {
81
        (ans += dp[root][i][0]) %= MOD;
82
        (ans += dp[root][i][1]) %= MOD;
83
        (ans += dp[root][i][2]) %= MOD;
84
    }
85
    cout << ans << endl;
86
}
87

88
signed main() {
89
    int T;
90
    cin >> T;
91
    while (T--)
92
        solve();
93
    return 0;
94
}

音乐

音乐

森林基站#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

样例解释#

数据范围#

文章分享

音乐

安吉D12-T2

森林基站#

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

样例解释#

数据范围#

文章分享