bzoj 4545
给定一个踹树，支持几种操作。
- 本质不同子串询问
- 加入子树
- 询问字符串\(S\) 在树上的出现次数。
好码好码
重点就是维护\(parent\) 树，考虑用\(LCT\)维护此树。
第三问就是匹配点的\(right\)集合大小，算一算就可以了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
int read () {
int q=0,f=1;char ch=getchar();
while(!isdigit(ch)) {
if(ch=='-')f=-1;ch=getchar();
}
while(isdigit(ch)){
q=q*10+ch-'0';ch=getchar();
}
return q*f;
}
long long ans;
int opt,x,y,n,q;
struct LCT {
int son[MAXN][2];
int fa[MAXN];
int v[MAXN];
int tag[MAXN];
int rev[MAXN];
int getson(int x) {
return son[fa[x]][1] == x;
}
int isroot(int x) {
return son[fa[x]][0] != x and son[fa[x]][1] != x;
}
void down(int now) {
swap(son[now][0],son[now][1]);
rev[now] ^= 1;
}
void Add_val(int x,int k) {
if(x) {
v[x] += k;
tag[x] += k;
}
}
void pushdown(int now) {
if(rev[now]) {
down(son[now][0]);
down(son[now][1]);
rev[now] = 0;
}
if(tag[now]) {
Add_val(son[now][0],tag[now]);
Add_val(son[now][1],tag[now]);
tag[now] = 0;
}
}
void dfs(int now) {
if(!isroot(now)) {
dfs(fa[now]);
}
pushdown(now);
}
void rotate(int now) {
int y = fa[now];
int z = fa[y];
int wht = getson(now);
fa[now] = z;
if(!isroot(y)) {
son[z][y == son[z][1]] = now;
}
fa[son[now][wht ^ 1]] = y;
son[y][wht] = son[now][wht ^ 1];
fa[y] = now;
son[now][wht ^ 1] = y;
}
void splay(int now) {
dfs(now);
for(int i = fa[now]; !isroot(now) ; rotate(now),i = fa[now]) {
if(!isroot(i)) {
rotate(getson(now) == getson(i) ? i : now);
}
}
}
void access(int now) {
for(int i = 0;now;i = now,now = fa[now]) {
splay(now);
son[now][1] = i;
}
}
void makeroot(int now) {
access(now);
splay(now);
down(now);
}
void link(int x,int y) {
makeroot(x);
fa[x] = y;
}
void cut(int x,int y) {
makeroot(x);
access(y);
splay(y);
son[y][0] = fa[x] = 0;
}
void Add(int x,int y,int k) {
makeroot(x);
access(y);
splay(y);
Add_val(y,k);
}
int query(int now) {
splay(now);
return v[now];
}
}lct;
struct SAM {
int ch[MAXN][3];
int len[MAXN];
int fail[MAXN];
int Cnt;
SAM() {
Cnt = 1;
}
int Copy(int c) {
int now = ++Cnt;
for(int i = 0;i <= 2; ++i) {
ch[now][i] = ch[c][i];
}
return now;
}
void link(int x,int y) {
fail[x] = y;
lct.link(x,y);
ans += len[x] - len[y];
}
int work(int p,int c) {
int q = ch[p][c];
int nq = Copy(q);
len[nq] = len[p] + 1;
lct.v[nq] = lct.query(q);
lct.cut(q,fail[q]);
ans -= len[q] - len[fail[q]];
link(nq,fail[q]);
link(q,nq);
for( ; ch[p][c] == q ; p = fail[p]) {
ch[p][c] = nq;
}
return nq;
}
int insert(int p,int c) {
int cur;
if(ch[p][c]) {
cur = len[ch[p][c]] == len[p] + 1 ? ch[p][c] : work(p,c);
}
else {
cur = ++Cnt;
len[cur] = len[p] + 1;
for( ; p and !ch[p][c] ; p = fail[p]) {
ch[p][c] = cur;
}
if(!p) {
link(cur,1);
}
else if(len[ch[p][c]] == len[p] + 1) {
link(cur,ch[p][c]);
}
else {
link(cur,work(p,c));
}
}
lct.Add(cur,1,1);
return cur;
}
}sam;
struct graph {
int head[MAXN];
int cnt;
graph () {
cnt = 0;
}
int ver[MAXN];
int nxt[MAXN];
int val[MAXN];
int vis[MAXN];
int pos[MAXN];
void add(int u,int v,int w) {
ver[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
val[cnt] = w;
}
void Add(int u,int v,int w) {
add(u,v,w);
add(v,u,w);
}
void dfs(int now) {
vis[now] = 1;
for(int i = head[now];i;i=nxt[i]) {
int y = ver[i];
if(vis[y]) {
continue;
}
pos[y] = sam.insert(pos[now],val[i]);
dfs(y);
}
}
}G;
char s[MAXN];
int main () {
x = read(),n = read();
for(int i = 1;i < n; ++i) {
x = read(),y = read();
scanf("%s",s);
G.Add(x,y,s[0] - 'a');
}
G.pos[1] = 1;
G.dfs(1);
q = read();
while(q--) {
opt = read();
if(opt == 1) {
cout<<ans<<endl;
}
else if(opt == 2) {
x = read(),y = read();
for(int i = 1;i < y; ++i) {
int X = read(),Y = read();
scanf("%s",s);
G.Add(X,Y,s[0] - 'a');
}
G.dfs(x);
}
else {
scanf("%s",s);int len = strlen(s);
int p = 1;
int tag = 1;
for(int i = 0;i < len; ++i) {
if(!sam.ch[p][s[i] - 'a']) {
cout<<0<<endl;
tag = 0;
break;
}
p = sam.ch[p][s[i] - 'a'];
}
if(tag) {
cout<<lct.query(p)<<endl;
}
}
}
return 0;
}