2014多校6 Another Letter Tree

Posted on Edited on In

2014多校6 Another Letter Tree

点分治做法

就裸地离个线，放到点分治上，从每个根开始，维护 \(dp_{u,l,r}\) 表示这条链匹配了序列中 \([l,r]\) 的部分

注意dp数组要一正一反，俩家伙一个含根一个不含

查询要合并两个dp数组，但是只需要知道 \(dp_{1,|s_0|}\) ，因此合并复杂度是 \(O(|s_0|)\) 的

最终复杂度，处理为 \(O(n\log n|s_0|^2+q|s_0|)\)

树剖线段树做法

类似上面的dp，线段树维护即可

问题1

需要存正反！

然后你发现内存从中间裂开！！

正反分两次，离线跑两次就可以了啊啊啊啊

问题2

如果直接查询合并，合并两个dp数组复杂度为 \(O(|s_0|^3)\)

查询复杂度为 \(O(q\log ^2n|s_0|^3)\)

妙啊!!比 \(n^2\) 还大!!

所以最后不能合并dp数组，而应该直接累加到答案数组上

问题3

没错现在我们的复杂度为 \(O(q\log ^2n|s_0|^2)\)

依然大得令人无法忍受

但是没想到吧，数据全部都是链，树剖是 \(O(1)\) 的

优化：查询重链时，只有最后依次是在链上查询 \([l,r]\) 都在中间的，而对于直接跳到top的部分，可以预处理出来

算上线段树的预处理，这样总复杂度就是 \(O(n|s_0|^3+q\log n |s_0|^2)\)

并查集做法

把问题拆成查询两条 \(u\) 到它的祖先 \(v\) 的答案

每个节点存储一个dp矩阵，用带权并查集维护

具体方法是:将询问按照 \(\text{LCA}\) 深度逆序排序后，每次查询一直将 \(u\) 合并到 \(v\) 为止

复杂度为 \(O(n\alpha(n)|s_0|^3)\) ，理论上来说，这个转移矩阵应当很稀疏，乘法应该很快，但是实际常数比较大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#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\n",Ans[i]);
	}
}

\[ \ \]

伪矩阵求逆做法

同样的，把问题拆成查询两条 \(u\) 到它的祖先 \(v\) 的答案(不包含v)

以从 \(v\) 到 \(u\) 的字符串为例，设 \(dp_u\) 为 \(u\) 的祖先链的dp矩阵，我们要求的部分答案是 \(x\)

则 \(dp_v\cdot 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共用了一个数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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\n",Que(x,y));
		}
	}
}