题目描述
传送门
题目大意： 给出一棵trie树 (1)询问当前trie的本质不同的子串数目是多少。 (2)以点rt为根向下长出一个子树，大小为si。 接下来si-1行，每行两个整数u,v和一个字符c，表示u号节点和v号节点之间有一条边，边上的字母为c。若长出子树之前当前树的大小是n，则这si-1点的编号分别为n+1,n+2…n+si-1。 (3)一个字符串S，询问字符串S在当前trie中的出现次数。
题解
广义后缀自动机 操作1：类似bzoj 4516: [Sdoi2016]生成魔咒,每次加入一个字符，对答案的贡献是ans+=l[x]-l[fa[x]] 操作2：直接加入即可 操作3：用lct维护每个点right集合的大小。类似bzoj 2555: SubString
代码
using namespace std;
int ch[
N][
2],son[
N][
30],father[N],fa[N],sum[N],l[N],tot,vis[N];
int n,m,point[N],nxt[N],v[N],val[N],root,np,q,p,nq,id,mp[N],st[N],top,cnt,last;
char s[N]; LL ans=0,size[N],delta[N];
void add(int x,int y,int z)
{
tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; val[tot]=z;
tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; val[tot]=z;
}
int isroot(int x)
{
return ch[
fa[x]][
1]!=x&&ch[
fa[x]][0]!=x;
}
int get(int x)
{
return ch[
fa[x]][1]==x;
}
void change(int x,LL v)
{
if (!x) return;
delta[x]+=v;
size[x]+=v;
}
void pushdown(int x)
{
if (delta[x]) {
change(ch[x][0],delta[x]);
change(ch[x][1],delta[x]);
delta[x]=0;
}
}
void rotate(int x)
{
int y=fa[x]; int z=fa[y]; int which=get(x);
if (!isroot(y)) ch[
z][
ch[z][
1]==y]=x;
fa[
x]=z; ch[
y][
which]=ch[
x][
which^1]; fa[
ch[x][
which^1]]=y;
ch[
x][
which^1]=y; fa[y]=x;
}
void splay(int x)
{
top=0; st[++top]=x;
for (int i=x;!isroot(i);i=fa[i])
st[++top]=fa[i];
for (int i=top;i>=1;i--) pushdown(st[i]);
int y;
while (!isroot(x)){
y=fa[x];
if (!isroot(y)) rotate(get(y)==get(x)?y:x);
rotate(x);
}
}
void access(int x)
{
int t=0;
while (x) {
splay(x);
ch[x][1]=t;
t=x; x=fa[x];
}
}
void cut(int x)
{
access(x);
splay(x);
change(ch[
x][
0],-size[x]);
ch[
x][
0]=fa[
ch[x][
0]]=0;
}
void link(int x,int y)
{
fa[y]=x;
access(x);
splay(x);
change(x,size[y]);
}
int extend(int c,int p)
{
np=++cnt;
l[np]=l[p]+1; size[np]=1;
for (;!son[
p][
c]&&p;p=father[
p]) son[
p][
c]=np;
if (!p) father[np]=root,link(root,np);
else {
q=son[p][c];
if (l[p]+1==l[q]) father[np]=q,link(q,np);
else {
nq=++cnt;
l[nq]=l[p]+1;
memcpy(son[nq],son[q],sizeof(son[nq]));
father[nq]=father[q];
link(father[nq],nq);
father[q]=father[np]=nq;
cut(q); link(nq,q);
link(nq,np);
for (;son[p][c]==q;p=father[p]) son[p][c]=nq;
}
}
ans+=(LL)(l[np]-l[father[np]]);
return np;
}
void dfs(int x,int f,int p,int c)
{
int t; vis[x]=1;
if (f==-1) t=mp[x];
else if (f==0) last=root=++cnt,t=root,mp[x]=root;
else t=extend(c,p),mp[x]=t;
for (int i=point[x];i;i=nxt[i])
if (!vis[v[i]]) dfs(v[i],x,t,val[i]);
}
int main()
{
freopen("a.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d",&id);
scanf("%d",&n);
for (int i=1;i
<n;i++) {
int x,y; char c[10];
scanf("%d%d%s",&x,&y,c);
add(x,y,c[0]-'a'+1);
}
dfs(1,0,0,0);
scanf("%d",&m);
for (int i=1;i<=m;i++) {
int opt;
scanf("%d",&opt);
if (opt==1) printf("%lld\n",ans);
if (opt==2) {
int rt,si; scanf("%d%d",&rt,&si);
for (int j=1;j<si;j++) {
int x,y; char c[10];
scanf("%d%d%s",&x,&y,c);
add(x,y,c[0]-'a'+1);
}
dfs(rt,-1,0,0);
}
if (opt==3) {
int now=root;
scanf("%s",s+1);
int len=strlen(s+1);
for (int j=1;j<=len;j++)
now=son[now][s[j]-'a'+1];
if(now==0) {
printf("0\n");
continue;
}
splay(now);
printf("%lld\n",size[now]);
}
}
}
