2014多校6 Another Letter Tree
4种做法略解
点分治做法
就裸地离个线，放到点分治上，从每个根开始，维护(dp_{u,l,r})表示这条链匹配了序列中([l,r])的部分
注意dp数组要一正一反，俩家伙一个含根一个不含
查询要合并两个dp数组，但是只需要知道(dp_{1,|s_0|})，因此合并复杂度是(O(|s_0|))的
最终复杂度，处理为(O(nlog n|s_0|^2+q|s_0|))
树剖线段树做法
类似上面的dp，线段树维护即可
问题1
需要存正反！
然后你发现内存从中间裂开！！
正反分两次，离线跑两次就可以了啊啊啊啊
问题2
如果直接查询合并，合并两个dp数组复杂度为(O(|s_0|^3))
查询复杂度为(O(qlog ^2n|s_0|^3))
妙啊!!比(n^2)还大!!
所以最后不能合并dp数组，而应该直接累加到答案数组上
问题3
没错现在我们的复杂度为(O(qlog ^2n|s_0|^2))
依然大得令人无法忍受
但是没想到吧，数据全部都是链，树剖是(O(1))的
优化：查询重链时，只有最后依次是在链上查询([l,r])都在中间的，而对于直接跳到top的部分，可以预处理出来
算上线段树的预处理，这样总复杂度就是(O(n|s_0|^3+qlog n |s_0|^2))
并查集做法
把问题拆成查询两条(u)到它的祖先(v)的答案
每个节点存储一个dp矩阵，用带权并查集维护
具体方法是:将询问按照( ext{LCA})深度逆序排序后，每次查询一直将(u)合并到(v)为止
复杂度为(O(nalpha(n)|s_0|^3))，理论上来说，这个转移矩阵应当很稀疏，乘法应该很快，但是实际常数比较大
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define reg register
#define Mod1(x) ((x>=P)&&(x-=P))
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
int s=0;
while(!isdigit(IO=getchar()));
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return s;
}
const int N=5e4+10,P=10007;
int n,m,len;
char str[N],t[N];
struct Node{
int a[31][31];
void clear(){ memset(a,0,sizeof a); }
void Init(int u) { clear(); rep(i,1,len) if(t[i]==str[u]) a[i][i]=1; }
Node operator + (const Node &x) const {
Node res; res.clear();
rep(i,1,len) for(int j=i;j<len && a[i][j];++j) for(int k=j+1;k<=len && x.a[j+1][k];++k) res.a[i][k]=(res.a[i][k]+a[i][j]*x.a[j+1][k])%P;
rep(i,1,len) rep(j,i,len) {
res.a[i][j]+=a[i][j],Mod1(res.a[i][j]);
res.a[i][j]+=x.a[i][j],Mod1(res.a[i][j]);
}
return res;
}
} s[N];
struct Edge{
int to,nxt;
}e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
e[++ecnt]=(Edge){v,head[u]};
head[u]=ecnt;
}
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int QX[N],QY[N],QL[N];
int dep[N],id[N],fa[N][18];
void pre_dfs(int u,int f) {
dep[u]=dep[fa[u][0]=f]+1;
rep(i,1,17) fa[u][i]=fa[fa[u][i-1]][i-1];
erep(u,i) {
int v=e[i].to;
if(v==f) continue;
pre_dfs(v,u);
}
}
int LCA(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=0,del=dep[x]-dep[y];(1<<i)<=del;++i) if(del&(1<<i)) x=fa[x][i];
if(x==y) return x;
drep(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int F[N],ans[N][31],Ans[N];
int Find(int x,int k=0) {
if(F[x]==x) return x;
int f=F[x]; F[x]=Find(f,k);
if(F[f]!=f){
if(!k) s[x]=s[x]+s[f];
else s[x]=s[f]+s[x];
}
return F[x];
}
int main(){
rep(kase,1,rd()) {
n=rd(),m=rd();
rep(i,1,n) head[i]=ecnt=0;
rep(i,2,n) {
int u=rd(),v=rd();
AddEdge(u,v),AddEdge(v,u);
}
scanf("%s%s",str+1,t+1),len=strlen(t+1);
pre_dfs(1,0);
rep(i,1,m) id[i]=i,QX[i]=rd(),QY[i]=rd(),QL[i]=LCA(QX[i],QY[i]);
sort(id+1,id+m+1,[&](int x,int y){ return dep[QL[x]]>dep[QL[y]]; });
rep(i,1,n) F[i]=i,s[i].clear();
rep(k,1,m){
int i=id[k],x=QX[i];
while(1){
int y=Find(x);
if(y==QL[i]) break;
F[y]=fa[y][0],s[y].Init(y);
}
ans[i][0]=1;
rep(j,1,len) ans[i][j]=s[x].a[1][j];
drep(j,len,1) if(str[QL[i]]==t[j]) ans[i][j]+=ans[i][j-1],Mod1(ans[i][j]);
}
rep(i,1,n) F[i]=i,s[i].clear();
rep(k,1,m){
int i=id[k],x=QY[i]; Ans[i]=0;
while(1){
int y=Find(x,1);
if(y==QL[i]) break;
F[y]=fa[y][0],s[y].Init(y);
}
rep(j,0,len-1) Ans[i]=(Ans[i]+ans[i][j]*s[x].a[j+1][len])%P;
Ans[i]=(Ans[i]+ans[i][len])%P;
}
rep(i,1,m) printf("%d
",Ans[i]);
}
}
[
]
伪矩阵求逆做法
同样的，把问题拆成查询两条(u)到它的祖先(v)的答案(不包含v)
以从(v)到(u)的字符串为例，设(dp_u)为(u)的祖先链的dp矩阵，我们要求的部分答案是(x)
则(dp_vcdot x=dp_u, x=frac{dp_u}{dp_v})
一般来说，矩阵求逆是一个很难实现的东西
但是发现对于一种(dp)，它的矩阵一定是一个上/下对角的矩阵
我们需要求出矩阵第一维为1或者第二维为(|s_0|)的部分
如果暴力求，可以看做求解一个(|s_0|)元的线性方程组，可以用高斯消元在(O(|s_0|^3))时间内求解
而实际上，这个线性方程组是含拓扑序关系的，任何一个含拓扑关系的线性方程组求解是不需要高斯消元的
而且这个问题列出的方程矩阵就已经是上对角矩阵了
所以写出来就是容斥吧
tips: 预处理部分一次只插入一个字符，复杂度为(O(n|s_0|^2)) (也可以认为是稀疏矩阵乘法)
查询部分求解线性方程复杂度为(O(|s_0|^2))，合并答案复杂度为(O(|s_0|))
因此复杂度为(O((n+q)|s_0|^2))
Code: 注意两种dp共用了一个数组
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
int s=0;
while(!isdigit(IO=getchar()));
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return s;
}
const int N=5e4+10,P=10007;
int n,m,len;
char str[N],t[N];
struct Edge{
int to,nxt;
}e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
e[++ecnt]=(Edge){v,head[u]};
head[u]=ecnt;
}
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
int dep[N],id[N],fa[N][18];
int dp[N][31][31];
int f1[31],f2[31];
void pre_dfs(int u,int f) {
dep[u]=dep[fa[u][0]=f]+1;
rep(i,1,17) fa[u][i]=fa[fa[u][i-1]][i-1];
rep(i,1,len) rep(j,1,len) {
dp[u][i][j]=dp[f][i][j];
if(str[u]==t[j]) {
if(i==j) dp[u][i][j]++,Mod1(dp[u][i][j]);
if(i<j) dp[u][i][j]+=dp[f][i][j-1],Mod1(dp[u][i][j]);
if(i>j) dp[u][i][j]+=dp[f][i][j+1],Mod1(dp[u][i][j]);
}
}
erep(u,i) {
int v=e[i].to;
if(v==f) continue;
pre_dfs(v,u);
}
}
int LCA(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=0,d=dep[x]-dep[y];(1<<i)<=d;++i) if(d&(1<<i)) x=fa[x][i];
if(x==y) return x;
drep(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void Calcdp1(int u,int f) {
rep(i,f1[0]=1,len) {
f1[i]=dp[u][i][1];
rep(j,0,i-1) f1[i]=(f1[i]-f1[j]*dp[f][i][j+1])%P;
Mod2(f1[i]);
}
}
void Calcdp2(int u,int f) {
drep(i,len,f2[len+1]=1) {
f2[i]=dp[u][i][len];
rep(j,i+1,len+1) f2[i]=(f2[i]-dp[f][i][j-1]*f2[j])%P;
Mod2(f2[i]);
}
}
int Que(int x,int y) {
int lca=LCA(x,y);
Calcdp1(x,fa[lca][0]),Calcdp2(y,lca);
int ans=0;
rep(i,0,len) ans=(ans+f1[i]*f2[i+1])%P;
return ans;
}
int main(){
rep(kase,1,rd()) {
n=rd(),m=rd();
rep(i,1,n) head[i]=ecnt=0;
rep(i,2,n) {
int u=rd(),v=rd();
AddEdge(u,v),AddEdge(v,u);
}
scanf("%s%s",str+1,t+1),len=strlen(t+1);
pre_dfs(1,0);
rep(i,1,m) {
int x=rd(),y=rd();
printf("%d
",Que(x,y));
}
}
}