题目
题目链接：https://gmoj.net/senior/#main/show/4498
给你一棵 \(n\) 个点的树，每个节点上有一个小写字母。有 \(m\) 个条件，每个条件给出两个点 \(x,y\)，表示 \(x\) 到 \(y\) 的路径组成的字符串是一个回文串。求满足所有条件的方案。两种方案不同当且仅当至少一个节点的字母不同。
\(n,m\leq 10^5\)。
思路
维护树上一个类似倍增的并查集。记 \(father[i][j][0/1]\) 表示点 \(i\) 到 \(i\) 的 \(2^j\) 级祖先的链（注意不包含第 \(2^j\) 级祖先）的并查集，\(0\) 表示从下往上，\(1\) 表示从上往下。
对于一个条件 \(x,y\)，设 \(dep[x]\geq dep[y]\)，记 \(p=\text{lca}(x,y)\)，把路径拆成两段，对于每一段，可以像 ST 表那样找到两个长度均为 \(2^k\) 的链，给并查集连边。
最后从大到小枚举 \(j\)，向 \(j-1\) 合并并查集即可。
时间复杂度 \(O((n+Q)\log n\times \alpha(n\log n))\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,LG=17,M=N*(LG+1)*2,MOD=1e9+7;
int n,Q,tot,head[N],dep[N],father[M],id1[N][LG+1][2],id2[M][3],f[N][LG+1];
ll ans,sum;
struct edge
{
int next,to;
}e[N*2];
void add(int from,int to)
{
e[++tot]=(edge){head[from],to};
head[from]=tot;
}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1; f[x][0]=fa;
for (int i=1;i<=LG;i++)
f[x][i]=f[f[x][i-1]][i-1];
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (v!=fa) dfs(v,x);
}
}
int lca(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (int i=LG;i>=0;i--)
if (dep[f[x][i]]>=dep[y]) x=f[x][i];
if (x==y) return x;
for (int i=LG;i>=0;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int find(int x)
{
return x==father[x]?x:father[x]=find(father[x]);
}
int jump(int x,int d)
{
int y=x;
for (int i=LG;i>=0;i--)
if (dep[x]-dep[f[y][i]]<=d) y=f[y][i];
return y;
}
int main()
{
freopen("paltree.in","r",stdin);
freopen("paltree.out","w",stdout);
memset(head,-1,sizeof(head));
scanf("%d",&n);
for (int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
tot=0; dfs(1,0); tot=0;
for (int i=1;i<=n;i++)
for (int j=0;j<=LG;j++)
{
id1[i][j][0]=++tot; id2[tot][0]=i; id2[tot][1]=j; id2[tot][2]=0;
id1[i][j][1]=++tot; id2[tot][0]=i; id2[tot][1]=j; id2[tot][2]=1;
father[tot]=tot; father[tot-1]=tot-1;
}
scanf("%d",&Q);
while (Q--)
{
int x,y;
scanf("%d%d",&x,&y);
if (dep[x]<dep[y]) swap(x,y);
int p=lca(x,y);
if (y!=p)
for (int i=0;i<=LG;i++)
if (dep[f[y][i+1]]<dep[p])
{
father[find(id1[x][i][0])]=find(id1[y][i][0]);
father[find(id1[x][i][1])]=find(id1[y][i][1]);
int d=dep[f[y][i]]-dep[p]+1;
x=jump(x,d); y=jump(y,d);
father[find(id1[x][i][0])]=find(id1[y][i][0]);
father[find(id1[x][i][1])]=find(id1[y][i][1]);
x=jump(x,dep[y]-dep[p]);
break;
}
if (x!=p)
for (int i=0;i<=LG;i++)
if (dep[f[x][i+1]]<dep[p])
{
int y=jump(x,dep[f[x][i]]-dep[p]+1);
father[find(id1[x][i][0])]=find(id1[y][i][1]);
father[find(id1[x][i][1])]=find(id1[y][i][0]);
break;
}
}
for (int j=LG;j>=1;j--)
for (int i=1;i<=n;i++)
for (int k=0;k<=1;k++)
{
int l=find(id1[i][j][k]);
if (l==id1[i][j][k]) continue;
int x=id2[l][0],y=id2[l][1],z=id2[l][2];
if (k==z)
{
father[find(id1[i][j-1][0])]=find(id1[x][y-1][0]);
father[find(id1[i][j-1][1])]=find(id1[x][y-1][1]);
father[find(id1[f[i][j-1]][j-1][0])]=find(id1[f[x][y-1]][y-1][0]);
father[find(id1[f[i][j-1]][j-1][1])]=find(id1[f[x][y-1]][y-1][1]);
}
else
{
father[find(id1[i][j-1][0])]=find(id1[f[x][y-1]][y-1][1]);
father[find(id1[i][j-1][1])]=find(id1[f[x][y-1]][y-1][0]);
father[find(id1[f[i][j-1]][j-1][0])]=find(id1[x][y-1][1]);
father[find(id1[f[i][j-1]][j-1][1])]=find(id1[x][y-1][0]);
}
}
ans=1;
for (int i=1;i<=n;i++)
{
if (find(id1[i][0][0])==id1[i][0][0]) sum++;
if (find(id1[i][0][1])==id1[i][0][1]) sum++;
if (find(id1[i][0][0])==id1[i][0][1]) sum++;
if (find(id1[i][0][1])==id1[i][0][0]) sum++;
}
for (int i=1;i<=sum/2;i++) ans=ans*26LL%MOD;
cout<<ans;
return 0;
}