【CF207C3】Game with Two Trees

【CF207C3】Game with Two Trees

Description

有两颗动态加入点的树，每条边有一个字符

每次加入完点后T1中到根的链在T2中的匹配次数之和

Input

一行一个数\(q\)

Output

输出\(q\)行每行一个数表示答案

Sample Input

5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a

Sample Output

1
3
3
4
7

Data Constraint

\(1\le q\le 10^5\)

Solution

给出一个无脑做法

先对T2建广义SAM，再做DAG链剖分

然后T1中每个点可以在DAG链上倍增+Hash找到对应点

接下来写两颗树状数组

分别支持区间加单点查和区间查单点加

复杂度\(O(q\log^2q)\)

Code

#include<bits/stdc++.h>
using namespace std;
#define Fo(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define N 100010
#define LL long long
#define ls x<<1
#define rs (x<<1)|1

namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T> void read(T& x){
		x=0; char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void write(T x,char c='\n'){
		if(x<0) pc('-'), x=-x;
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
using IO::gc;

int mod(int x){return x>=mo?x-mo:x;}

int pw[N*2],ipw[N*2];
int n1,n2,id[N*2];
struct node{int ty,u;char ch;}ask[N*2];
vector<int>e1[N*2],e2[N*2];
int num1[N*2],num2[N*2];
struct Trie{
	int tot,ch[N*2][26];
	int insert(int x,int tr){
		ch[x][tr]?x=ch[x][tr]:x=ch[x][tr]=++tot;
		return x;
	}
	void build(int u,int p){
		id[u]=p;
		for(auto v:e2[u])build(v,insert(p,num2[v]));
	}
}T;
struct SAM{
	vector<int>e[N*2];
	LL s1[N*2],s2[N*2]; 
	int ch[N*2][26],link[N*2],len[N*2],u,rt,tot,lst[N*2];
	int nxt[N*2],pre[N*2],son[N*2],rk[N*2],top[N*2],wh[N*2],num;
	int line[N*2],cnt,d[N*2];
	int g[N*2],pos[N*2];
	int *tg[N*2],*tp[N*2];
	int vis[N*2],sz[N*2];
	int dfn[N*2],siz[N*2],ta;
	int extend(int v,int p){
		int u=++tot;
		for(;v&&!ch[v][p];v=link[v])ch[v][p]=u,len[u]=max(len[u],len[v]+1);
		if(!v)link[u]=rt;
		else if(len[ch[v][p]]==len[v]+1)link[u]=ch[v][p];
		else{
			int clone=++tot,Old=ch[v][p];
			len[clone]=len[v]+1;
			Fo(j,0,25)ch[clone][j]=ch[Old][j];
			link[clone]=link[Old];
			link[Old]=link[u]=clone;
			for(;v&&ch[v][p]==Old;v=link[v])ch[v][p]=clone;
		}
		return u;
	}
	void build(){
		rt=lst[1]=tot=1;
		queue<int>q;
		q.push(1);
		while(!q.empty()){
			int u=q.front();q.pop();
			Fo(i,0,25)if(T.ch[u][i]){
				int v=T.ch[u][i];
				lst[v]=extend(lst[u],i);
				q.push(v);
			}
		}
		Fo(i,1,tot)e[link[i]].push_back(i);
	}
	void dfs(int u){
		dfn[u]=++ta;siz[u]=1;
		for(auto v:e[u])dfs(v),siz[u]+=siz[v];
	}
	void DAG(){
		queue<int>q;
		Fo(i,1,tot) Fo(j,0,25)if(ch[i][j])d[ch[i][j]]++;
		q.push(1);
		while(!q.empty()){
			int u=q.front();q.pop();
			line[++cnt]=u;
			Fo(i,0,25)if(ch[u][i]){
				d[ch[u][i]]--;
				if(!d[ch[u][i]])q.push(ch[u][i]);
			}
		}
		Fd(i,cnt,1){
			int u=line[i];s1[u]++;
			Fo(j,0,25)if(ch[u][j]){
				if(s1[ch[u][j]]>s1[nxt[u]])nxt[u]=ch[u][j];
				s1[u]+=s1[ch[u][j]];
			}
		}
		Fo(i,1,cnt){
			int u=line[i];s2[u]++;
			Fo(j,0,25)if(ch[u][j]){
				if(s2[u]>s2[pre[ch[u][j]]])pre[ch[u][j]]=u;
				s2[ch[u][j]]+=s2[u];
			}
		}
		Fo(i,1,tot) Fo(j,0,25)if(ch[i][j]){
			if(nxt[i]==ch[i][j]&&pre[ch[i][j]]==i)son[i]=ch[i][j],wh[i]=j+1;
		}
		int tmp=0;
		Fo(i,1,tot){
			int u=line[i];
			if(vis[u])continue;
			int v=u;
			sz[u]=1;rk[u]=++num;top[u]=u;
			while(son[v])sz[u]++,v=son[v],rk[v]=++num,top[v]=u;
			tg[u]=g+tmp;
			tp[u]=pos+tmp;
			v=u;
			int val=0;
			Fo(j,1,sz[u]){
				vis[v]=1;
				tg[u][j-1]=val;
				tp[u][j-1]=v;
				val=mod(val+1ll*pw[j-1]*wh[v]%mo);
				v=son[v];
			}
			tmp+=sz[u];
		}
	}
}S;
struct BIT{
	int sum[N*2];
	int lowbit(int x){return -x&x;}
	void change(int x,int y){for(;x<=S.tot;x+=lowbit(x))sum[x]+=y;}
	int query(int x){int res=0;for(;x;x-=lowbit(x))res+=sum[x];return res;}
}T1,T2;

int dep[N*2],fa[N*2][20],val[N*2],q;
LL ans;

int main(){
	pw[0]=ipw[0]=1;
	Fo(i,1,N*2-10){
		pw[i]=37ll*pw[i-1]%mo;
		ipw[i]=242816194ll*ipw[i-1]%mo;
	}
	n1=n2=1;
	read(q);
	Fo(i,1,q){
		int ty,u;char s[3];
		read(ty);read(u);s[1]=gc();
		ask[i]=(node){ty,ty==1?n1+1:n2+1,s[1]};
		if(ty==1){
			n1++;
			fa[n1][0]=u;
			dep[n1]=dep[u]+1;
			e1[u].push_back(n1);
			num1[n1]=s[1]-'a';
		}
		if(ty==2){
			n2++;
			e2[u].push_back(n2);
			num2[n2]=s[1]-'a';
		}
	}
	T.tot=1;
	T.build(1,1);
	S.build();
	S.DAG();
	S.dfs(1);
	Fo(i,1,n1) Fo(j,0,18)fa[i][j+1]=fa[fa[i][j]][j];
	Fo(i,2,n1)val[i]=mod(37ll*val[fa[i][0]]%mo+num1[i]+1);
	T1.change(1,1);T1.change(S.tot+1,-1);
	T2.change(1,1);
	ans=1;
	Fo(i,1,q){
		if(ask[i].ty==1){
			int u=1,wh=ask[i].u,flag=1;
			while(wh!=1){
				int up=S.top[u],lu=S.rk[u]-S.rk[up];
				int res=min(dep[wh],S.sz[up]-lu),tmp=lu;
				Fd(j,19,0)if(res>=(1<<j)){
					if(1ll*mod(val[wh]-1ll*val[fa[wh][j]]*pw[1<<j]%mo+mo)*pw[tmp]%mo==mod(S.tg[up][tmp+(1<<j)]-S.tg[up][tmp]+mo)){
						wh=fa[wh][j];tmp+=1<<j;res-=1<<j;
					}
				}
				u=S.tp[up][tmp];
				if(wh!=1){
					if(!S.ch[u][num1[wh]]){flag=0;break;}
					u=S.ch[u][num1[wh]];
					wh=fa[wh][0];
				}
			}
			if(flag){
				ans+=T2.query(S.dfn[u]+S.siz[u]-1)-T2.query(S.dfn[u]-1);
				T1.change(S.dfn[u],1);T1.change(S.dfn[u]+S.siz[u],-1);
			}
		}else{
			ans+=T1.query(S.dfn[S.lst[id[ask[i].u]]]);
			T2.change(S.dfn[S.lst[id[ask[i].u]]],1);
		}
		write(ans);
	}
	return 0;
}