隐藏
「bzoj4231」回忆树 - KMP+AC自动机/后缀自动机 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj4231」回忆树 - KMP+AC自动机/后缀自动机

题目大意

    回忆树是树。
    具体来说,是$n$个点$n-1$条边的无向连通图,点标号为$1\sim n$,每条边上有一个字符(出于简化目的,我们认为只有小写字母)。
    对一棵回忆树来说,回忆当然是少不了的。
    一次回忆是这样的:你想起过往,触及心底…唔,不对,我们要说题目。
    这题中我们认为回忆是这样的:给定$2$个点$u,v$($u$可能等于$v$)和一个非空字符串$s$,问从$u$到$v$的简单路径上的所有边按照到$u$的距离从小到大的顺序排列后,边上的字符依次拼接形成的字符串中给定的串$s$出现了多少次。


题目分析

这道题显然在线不可做,转为尝试转为离线询问。

在树上的字符串问题总是转化为到根的一段路径,而题目询问的是树上任意一段路径。
我们可以将询问串可能出现的位置分为,从$u\rightarrow lca$,$x\rightarrow lca\rightarrow y$,$lca\rightarrow v$三段,其中$x,y$是前后两段路径中的一个点,满足$dep_x-dep_{lca}=len,dep_y-dep_{lca}=len$,其中$len$是询问串长度,注意若不存在$x$或$y$满足条件,即令$x=u$或$y=v$。
注意到询问串总长$\le300000$,故中间段$x\rightarrow lca\rightarrow y$可以暴力KMP匹配,时间复杂度$O(2\times300000)$。

剩下可能出现的位置仅剩$u\rightarrow lca$,$lca\rightarrow v$两段。
这样就转化为到根的一条链了,注意$u\rightarrow lca$顺序是反的,故在AC自动机上插入询问串与询问串的反串。
找到串结束端点可能出现的位置$u\rightarrow x,v\rightarrow y$,打上标记准备离线扫描。

标记方法为,在$u,v$处$+1$,在$x,y$处$-1$,表示统计这一段路径的答案,并记录下询问串在AC自动机上的位置。
接下来遍历原树,使用树状数组统计fail树上的答案,加加减减得出每个询问的解。


代码

代码抄的Claris的。

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
int Get_Int() {
int res=0,bj=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;

const int maxn=100005,maxl=600005;

struct Edge {
int from,to;
char ch;
};

int Size[maxn],father[maxn],Depth[maxn],Son[maxn],Dfn[maxn],step=0,M[maxn],Top[maxn];
char ch[maxn];
vector<Edge> edges[maxn];

void Dfs(int Now,int fa,int depth) {
Size[Now]=1;
father[Now]=fa;
Depth[Now]=depth;
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==fa)continue;
ch[Next]=e.ch;
Dfs(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Next]>Size[Son[Now]])Son[Now]=Next;
}
}

void Dfs2(int Now,int top) {
Dfn[Now]=++step;
M[step]=Now;
Top[Now]=top;
if(Son[Now])Dfs2(Son[Now],top);
for(Edge& e:edges[Now]) {
int Next=e.to;
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}

int LCA(int x,int y) {
for(; Top[x]!=Top[y]; x=father[Top[x]])if(Depth[Top[x]]<Depth[Top[y]])swap(x,y);
return Depth[x]<Depth[y]?x:y;
}

int kth(int x,int k) { //k倍祖先
while(k>Depth[x]-Depth[Top[x]])
k-=Depth[x]-Depth[Top[x]]+1,x=father[Top[x]];
return M[Dfn[x]-k];
}

struct KMP {
int Next[maxn];

void Get_Next(char* s) { //ACAM like KMP
int len=strlen(s);
Next[0]=-1;
for(int i=1,j=-1; i<len; Next[i++]=j) {
while(~j&&s[i]!=s[j+1])j=Next[j];
if(s[i]==s[j+1])j++;
}
}

void solve(int x,int y,int lca,char* s,int &ans) {
int len=strlen(s);
int l=kth(x,Depth[x]-min(Depth[x],Depth[lca]+len-1)),r=kth(y,Depth[y]-min(Depth[y],Depth[lca]+len-1));
Get_Next(s);
int j=-1;
for(; l!=lca; l=father[l]) {
while(~j&&s[j+1]!=ch[l])j=Next[j];
if(s[j+1]==ch[l])j++;
if(j==len-1)ans++,j=Next[j];
}
static int tmp[maxl];
int cnt=0;
for(; r!=lca; r=father[r])tmp[++cnt]=ch[r];
for(; cnt; cnt--) {
while(~j&&s[j+1]!=tmp[cnt])j=Next[j];
if(s[j+1]==tmp[cnt])j++;
if(j==len-1)ans++,j=Next[j];
}
}
} kmp;

struct Aho_Corasick_Automaton {
struct Tree {
int child[26],fail;
} tree[maxl];
int root,cnt,First[maxl],Last[maxl];
vector<int> edges[maxl];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

#define ch(x,i) tree[x].child[i]
#define fail(x) tree[x].fail

Aho_Corasick_Automaton() {
init();
}

void init() {
root=cnt=1;
memset(tree,0,sizeof(tree));
}

int insert(string s) {
int now=root;
for(auto x:s) {
int j=x-'a';
if(!ch(now,j))ch(now,j)=++cnt;
now=ch(now,j);
}
return now;
}

void dfs(int Now) {
First[Now]=++step;
for(int Next:edges[Now])dfs(Next);
Last[Now]=step;
}

void buildfail() {
queue<int>Q;
Q.push(root);
while(!Q.empty()) {
int now=Q.front();
Q.pop();
for(int i=0; i<26; i++) {
int& next=ch(now,i);
if(!next) {
next=ch(fail(now),i)?ch(fail(now),i):root;
continue;
}
Q.push(next);
int p=fail(now);
if(p)fail(next)=ch(p,i);
else fail(next)=root;
}
}
for(int i=2; i<=cnt; i++)AddEdge(fail(i),i);
dfs(root);
}
} acam;

struct BIT {
int c[maxl];
#define lowbit(x) x&(-x)
void add(int x,int v) {
for(int i=acam.First[x]; i<=acam.cnt; i+=lowbit(i))c[i]+=v;
}
int sum(int x) {
int ans=0;
for(int i=x; i>=1; i-=lowbit(i))ans+=c[i];
return ans;
}
int ask(int x) {
return sum(acam.Last[x])-sum(acam.First[x]-1);
}
} bit;

struct Query {
int pos,id,bj;
};

vector<Query> q[maxn];

void AddEdge(int x,int y,char v) {
edges[x].push_back((Edge) {x,y,v});
}

void AddQuery(int x,int now,int id,int bj) {
q[x].push_back((Query) {now,id,bj});
}

int n,m,ans[maxn];
char s[maxn];

void dfs(int Now,int acpos) {
bit.add(acpos,1);
for(auto x:q[Now]) {
if(x.bj>0)ans[x.id]+=bit.ask(x.pos);
else ans[x.id]-=bit.ask(x.pos);
}
for(Edge &e:edges[Now])
if(e.to!=father[Now])dfs(e.to,acam.tree[acpos].child[e.ch-'a']);
bit.add(acpos,-1);
}

int main() {
n=Get_Int();
m=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
char ch=' ';
while(!isalpha(ch))ch=getchar();
AddEdge(x,y,ch);
AddEdge(y,x,ch);
}
Dfs(1,0,1);
Dfs2(1,1);
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
scanf("%s",s);
int len=strlen(s),lca=LCA(x,y);
kmp.solve(x,y,lca,s,ans[i]);
if(Depth[y]-Depth[lca]>=len) {
int now=acam.insert(s);
AddQuery(y,now,i,1);
AddQuery(kth(y,Depth[y]-Depth[lca]-len+1),now,i,-1);
}
if(Depth[x]-Depth[lca]>=len) {
reverse(s,s+len);
int now=acam.insert(s);
AddQuery(x,now,i,1);
AddQuery(kth(x,Depth[x]-Depth[lca]-len+1),now,i,-1);
}
}
step=0;
acam.buildfail();
dfs(1,1);
for(int i=1; i<=m; i++)printf("%d\n",ans[i]);
return 0;
}

姥爷们赏瓶冰阔落吧~