远古模拟赛里的一道题，前来写篇题解记录一下。
我们考虑一个显然的转化。将每条边染色，那么原问题等价于求下面的染色的方案数：
对于每个点对 \(a,b\)，我们记 \(\operatorname{lca}(a,b)=c\) 有
- \(a\sim c\) 上的所有边同色。
- \(b\sim c\) 上的所有边同色。
- \(a\sim c\) 和 \(b\sim c\) 上的边不同色。
再次转化。构造一张图 \((*)\)，这张图上的每个点是原图的一条边。这张图满足对于每一对 \(a,b,c\)，\(a/b\sim c\) 上的所有边（新图的点）用蓝色边连接，且对于 \(c\not =a,b\) 用红色边连接 \((a,fa[a])\) 和 \((b,fa[b])\)。
现在问题就转化成了，对这张新图的点染色，使得用蓝色边连接的点颜色相同，用红色边连接的节点颜色不同。显然我们先分别求每个连通块的结果即可。
这样考虑的话，我们发现一个节点的颜色唯一确定了这张图的所有点的颜色。这也同时意味着，如果存在一个合理的涂色方案，我们对这张图完全颜色反转，结果没有变化。因此我们只需要处理连通块是否不存在合法方案，搜一下就行。这样我们经过多次转化，问题可以轻易解决。如果存在不合法的连通块，答案为 \(0\)，否则是 \(2^m\)，其中 \(m\) 为连通块数量。
现在的问题就是，我们如何构造图 \((*)\)。如果我们暴力的建图，时间复杂度爆炸。我们考虑 \((x,fa
[x])\) 是否和 \((fa[x],fa[fa[x]])\) 用蓝色边连接，可以另写一个函数 \(\operatorname{connect}(x)\)，他返回一个节点已向 \(x\) 子树中的节点连蓝色边的最小深度。这个函数值取决于它子节点的值和直接向 \(x\) 连蓝色边的点的深度。后者可以直接用每个给定点对的 LCA 更新即可。
时间复杂度 \(O((m+n)\log n)\)。
核心代码如下：
int connect(int x, int p) {
for (auto it : E[x])
if (it != p) {
int tmp = connect(it, x);
high[x] = min(high[x], tmp);
if (tmp < depth[x])
add_edge(it, x, 0);
}
return high[x];
}
int main(){
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
int c = lca(a, b);
hi[a] = min(hi[a], depth[c]);
hi[b] = min(hi[b], depth[c]);
if (a != c && b != c)
add_edge(a, b, 1);
}
}
connect(1, 0);