看题目限制，可以发现如果将机器人作为点，指控和保护关系作为边，可以建出一个森林，就下来就是传统的树形背包了。
设 \(f_{i,j,0/1}\) 表示当前点为 \(i\)，子树内有 \(j\) 个狼人，当前点是否为狼人的方案数。
初始化：\(f_{u,0,0} = f_{u,1,1} = 1\)
当前点为狼：
- 指控：\(f_{u,j,1}=f_{u,j-k,1} \times f_{v,k,0}\)
- 保护：\(f_{u,j,1}=f_{u,j-k,1} \times f_{v,k,1}\)
当前点为民：\(f_{u,j,0}=f_{u,j-k,0} \times (f_{v,k,0}+f_{v,k,1})\)
最后还需要把没棵树合并起来：\(g_j=g_{j-k} \times (f_{i,k,0}+f_{i,k,1})\)
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200 + 5, mod = 1e9 + 7;
int n, num, m, vis[N];
ll f[N][N][2], tmp[N][2], g[N];
struct node{
int v, w;
node(int v = 0, int w = 0):v(v), w(w){}
};
vector<node> adj[N];
void dfs(int u) {
vis[u] = 1;
f[u][0][0] = f[u][1][1] = 1;
for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i].v);
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].v, w = adj[u][i].w;
memset(tmp, 0, sizeof(tmp));
for (int j = num; j >= 1; --j) {
for (int k = 0; k < j; ++k) {
tmp[j][1] = (tmp[j][1] + f[u][j - k][1] * f[v][k][w]) % mod;
}
}
for (int j = num; j >= 1; --j) f[u][j][1] = tmp[j][1];
}
for (int i = 0; i < adj[u].size(); ++i) {
int v = adj[u][i].v, w = adj[u][i].w;
memset(tmp, 0, sizeof(tmp));
for (int j = num; j >= 1; --j) {
for (int k = 0; k <= j; ++k) {
tmp[j][0] = (tmp[j][0] + f[u][j - k][0] * (f[v][k][0] + f[v][k][1])) % mod;
}
}
for (int j = num; j >= 1; --j) f[u][j][0] = tmp[j][0];
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> num >> m;
for (int i = 1; i <= m; ++i) {
char type; int u, v;
cin >> type >> u >> v;
adj[u].push_back(node(v, (type == 'D')));
}
g[0] = 1;
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
dfs(i);
memset(tmp, 0, sizeof(tmp));
for (int j = num; j >= 1; --j) {
for (int k = 0; k <= j; ++k) {
tmp[j][0] = (tmp[j][0] + g[j - k] * (f[i][k][0] + f[i][k][1])) % mod;
}
}
for (int j = num; j >= 1; --j) g[j] = tmp[j][0];
}
}
cout << g[num] << endl;
return 0;
}