压缩特殊节点后的子集动态规划（通过子任务 1–2，共 16 分）

适用于子任务 $1,2$，即 $N\le20$。只给普通节点 $3,\ldots,N$ 编号到一个集合中，令其数量为 $m=N-2$。

压缩特殊节点之间的移动

从一个普通节点出发，在喜欢的颜色固定时，通向 $1,2$ 的两条边颜色相反，所以恰有一个特殊节点可以直接到达。到达后，可以立即离开，也可以再经过另一个特殊节点；不能再走第三个特殊节点，否则立即折返。

从 $1$ 出发只能沿蓝边进入白色普通节点，从 $2$ 出发只能沿红边进入白色普通节点。因此，从任意一个普通节点状态出发，经一个或两个特殊节点到达下一个白色普通节点，有且仅有两种方式：最后从 $1$ 进入，颜色为蓝；或者最后从 $2$ 进入，颜色为红。

同样，从任一普通节点状态到达 $2$ 并结束，有且仅有一种不再访问普通节点的方式：若可直接到达的是 $2$ 就停止，否则先到 $1$ 再到 $2$。起始阶段也有两种进入第一个白色普通节点的方式，即从 $1$ 直接进入，或先到 $2$ 再进入。

这些压缩不会引入立即折返。下一普通节点必须尚未访问；在普通节点处反向走刚才的边又需要相反颜色，而普通节点不改变颜色；特殊节点之间则明确只允许走一条直接边。

集合状态与转移

定义 $f(S,u,c)$ 为已访问普通节点集合恰为 $S$、当前位置是 $u\in S$、喜欢颜色为 $c$ 的合法前缀数量。两个颜色都保留，空集合没有普通节点结尾，初始所有 $f$ 为零。

令

$$g(S)=[S=\varnothing]+\sum_{u\in S}\sum_{c\in\{\text{红},\text{蓝}\}}f(S,u,c).$$

其中 $g(\varnothing)=1$ 代表从 $1$ 开始、还没有访问普通节点的初始状态。

对每个尚未访问的普通节点 $v\notin S$，分两类更新。

若 $v$ 为白色，则通过特殊节点进入 $v$ 的转移为

$$\begin{aligned} f(S\cup\{v\},v,\text{蓝})&\mathrel{+}=g(S),\\ f(S\cup\{v\},v,\text{红})&\mathrel{+}=g(S). \end{aligned}$$

另外，对于 $u\in S$，若 $u\to v$ 为颜色 $c$ 的边，可以直接移动而不改变颜色：

$$f(S\cup\{v\},v,c)\mathrel{+}=f(S,u,c).$$

直接移动与经过特殊节点的移动对应不同节点序列，应分别累加。每次转移都会增加一个普通节点，按集合掩码递增计算即可。

最终答案为

$$\sum_{S\subseteq\{3,\ldots,N\}}g(S).$$

非空集合的每个前缀都有唯一的“到 $2$ 后结束”方式；空集合贡献直接行走 $1\to2$。每条完整行走由最后一个普通节点及其前缀唯一确定，所以该求和没有重计。所有运算对 $10^9+7$ 取模。

时间复杂度为 $O(m^2 2^m)$，每个集合枚举前后两个普通节点；空间复杂度为 $O(m2^m)$，保留完整的集合、末端节点、颜色三维表。$m\le18$ 时可行，较大的 $N$ 会使指数空间超过限制。

参考代码（C++20）

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  constexpr int mod = 1000000007;
  int m = n - 2;
  i64 count = 1LL << m;
  vector<vector<vector<int>>> dp(count, vector<vector<int>>(m, vector<int>(2)));
  int ans = 0;
  auto add = [&](int& res, int value) {
    res += value;
    if (res >= mod) res -= mod;
  };
  for (i64 mask = 0; mask < count; mask++) {
    int sum = (mask == 0);
    for (int u = 0; u < m; u++) {
      for (int value : dp[mask][u]) add(sum, value);
    }
    add(ans, sum);
    for (int v = 0; v < m; v++) {
      if (mask >> v & 1) continue;
      i64 nxt = mask | (1LL << v);
      if (s[v + 2] == 'W') {
        add(dp[nxt][v][0], sum);
        add(dp[nxt][v][1], sum);
      }
      for (int u = 0; u < m; u++) {
        if (!(mask >> u & 1)) continue;
        int blue = (u < v) != (s[u + 2] == s[v + 2]);
        add(dp[nxt][v][blue], dp[mask][u][blue]);
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}