题目理解

我们有一个 $N$ 个节点的有向树森林（由题目保证 $A < B$ 可知边从小编号指向大编号，无环），每个节点可以有两种身份：狼人（用 1 表示）或村民（用 0 表示）。
已知总共有 $W$ 个狼人，并且有 $M$ 条指控或保护关系，每条关系是：

• A a b：表示 $a$ 指控 $b$ 是狼人
• D a b：表示 $a$ 保护 $b$

狼人的行为规则：

1. 狼人从不指控其他狼人（即若 $a$ 是狼人且存在 A a b，则 $b$ 必须是村民）
2. 狼人保护的都是其他狼人（即若 $a$ 是狼人且存在 D a b，则 $b$ 必须是狼人）

村民可以任意指控或保护任何人。

此外：

• 没有节点同时被指控和被保护
• 没有节点被指控或保护超过一次
• 所有边满足 $a < b$，因此是 DAG（实际是森林）

我们需要计算满足这些条件的角色分配方案数，结果对 $10^9+7$ 取模。

---

思路分析

1. 问题转化

由于 $a < b$，图是一个有向森林，我们可以从叶子往根（编号大的往小的）做树形 DP。

定义 $dp[u][j][0/1]$ 表示在以 $u$ 为根的子树中，分配了 $j$ 个狼人，且 $u$ 的身份是 0（村民）或 1（狼人）时的方案数。

2. 状态转移

初始状态：对于叶子节点 $u$，$dp[u][0][0] = 1$，$dp[u][1][1] = 1$。

对于节点 $u$ 和它的一个子节点 $v$，根据边的类型（A 或 D）进行合并：

• 如果边是 A（指控）：
  • 若 $u$ 是狼人，则 $v$ 必须是村民（规则 1）
  • 若 $u$ 是村民，则 $v$ 可以是狼人或村民
• 如果边是 D（保护）：
  • 若 $u$ 是狼人，则 $v$ 必须是狼人（规则 2）
  • 若 $u$ 是村民，则 $v$ 可以是狼人或村民

转移时用临时数组 $tmp$ 暂存合并后的结果，避免覆盖。

3. 森林处理

由于可能是森林（多个连通分量），我们对每个未访问的根节点做一次 DFS，然后用背包合并所有连通分量的方案。

最终 $f[W]$ 就是答案。

---

代码步骤解析

1. 输入与建图

cin >> n >> w >> m;
for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> opt >> x >> y;
    addedge(x, y, opt[0] == 'A');
}

• 用邻接表存储树边，edge[i] = 0 表示保护关系，edge[i] = 1 表示指控关系。

2. 树形 DP

void dfs(int x) {
    vis[x] = 1;
    dp[x][0][0] = dp[x][1][1] = 1; // 初始状态

    for (int i = head[x]; i != -1; i = nxt[i]) {
        int y = ver[i];
        dfs(y);
        memset(tmp, 0, sizeof(tmp));

        for (int j = n; j >= 0; j--)
            for (int k = 0; k <= j; k++) {
                // u 是村民
                tmp[j][0] = (tmp[j][0] + 1LL * dp[x][k][0] * dp[y][j-k][0] % mod) % mod;
                tmp[j][0] = (tmp[j][0] + 1LL * dp[x][k][0] * dp[y][j-k][1] % mod) % mod;
                
                // u 是狼人
                if (edge[i] == 0) // D 保护：v 必须是狼人
                    tmp[j][1] = (tmp[j][1] + 1LL * dp[x][k][1] * dp[y][j-k][1] % mod) % mod;
                if (edge[i] == 1) // A 指控：v 必须是村民
                    tmp[j][1] = (tmp[j][1] + 1LL * dp[x][k][1] * dp[y][j-k][0] % mod) % mod;
            }
        memcpy(dp[x], tmp, sizeof(tmp));
    }
}

3. 森林合并

f[0] = 1;
for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    dfs(i);
    memset(g, 0, sizeof(g));
    for (int j = w; j >= 0; j--)
        for (int k = 0; k <= j; k++) {
            g[j] = (g[j] + 1LL * f[j-k] * dp[i][k][0] % mod) % mod;
            g[j] = (g[j] + 1LL * f[j-k] * dp[i][k][1] % mod) % mod;
        }
    memcpy(f, g, sizeof(f));
}
cout << f[w];

---

复杂度分析

• 时间复杂度：$O(N^3)$，因为树形 DP 中每对 $(j,k)$ 的组合需要遍历。
• 空间复杂度：$O(N^2)$，存储 DP 数组。

---

示例验证

样例 1

2 1 1
D 1 2

• 唯一方案：节点 2 是狼人，节点 1 是村民
• 输出：1

样例 2

2 1 0

• 两个方案：(1狼2民) 或 (1民2狼)
• 输出：2

样例 3

3 2 2
A 1 2
D 1 3

• 两种方案：
  1. 节点 1 狼，节点 2 民，节点 3 狼
  2. 节点 1 民，节点 2 狼，节点 3 狼
• 输出：2

---

算法标签

• 树形 DP
• 组合计数
• 有向无环图

---

总结

本题通过树形动态规划处理狼人游戏中的身份分配问题，利用 $a < b$ 的性质构建 DAG，从叶子向根递推，同时根据指控和保护关系的不同约束条件进行状态转移，最终用背包合并森林中多棵树的方案数。