很典型的容斥，令f(S)f(S)f(S)表示SSS中所有路径上的所有边均为白色的方案数，令输入的路径集合为PPP，那么： 然后枚举子集，计算 f(S)f(S)f(S) 即可，设 SSS 中所有路径的并所占边数为 x，则 f(S)=2n−1−xf(S)=2 ^n−1−xf(S)=2n−1−x ，即除了这 x 条边以外都是任意染色的。 于是计算路径并的边数 x 即可，每个子集都暴力做太慢了，总复杂度是 O(2m×nm)O(2 ^m ×nm)O(2m×nm)，可以采用递推的思想，考虑一个 p∈Sp∈Sp∈S，SSS 的 xxx 值可以由 S/pS/{p}S/p 的 x 值并上 ppp 的边得到，这样可以 O(2m×n)O(2^m×n)O(2m×n)。 最后，还可以再用 bitsetbitsetbitset 优化一下常数。

#include <iostream> #include <vector> #include <queue> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 55; // 顶点数 const int MAXM = 20; // 约束数 vector<pair<int, int>> G[MAXN]; // 树：邻接表存 (to, edge_id) ll edge_mask[MAXM]; // 第i个约束路径对应的边集合（二进制mask） int N, M; // BFS 找 u->v 路径上的所有边，返回二进制mask ll get_path_mask(int u, int v) { queue<int> q; int from[MAXN], eid[MAXN]; // from: 前驱点 eid: 前驱边 memset(from, -1, sizeof(from)); q.push(u); from[u] = u; } int main() { ios::sync_with_stdio(false); cin.tie(0); }