题目大意

　　给你一颗trie树，令\(s_i\)为点\(i\)到根的路径上的字符组成的字符串。求\(max_{u\neq v}(LCP(s_u,s_v)+LCS(s_u,s_v))\)

　　\(LCP=\)最长公共前缀，\(LCS=\)最长公共后缀

　　\(1\leq n\leq 200000\)，字符集为\(\{0\ldots 300\}\)

题解

　　我们先看看这个\(LCP(s_u,s_v)\)怎么求

　　广义后缀自动机不行。广义后缀树可能可以，但我不会。广义后缀数组可以。然后我就开始手推广义后缀数组

　　广义后缀数组：和后缀数组类似，求出\(s_i\)的排名以及\(LCP(s_{sa_{}i-1},s_{sa_i})\)

　　实现也和后缀数组类似，倍增，把两段\(2^{i-1}\)的信息合并成\(2^i\)的信息。另外还要保存\(s_i\)的长度为\(2^j\)的前缀在所有字符串的长度为\(2^j\)的前缀中的排名。

　　求完\(sa_i\)和\(rk_i\)后，我们用二分+哈希求\(LCP(s_{sa_{i-1}},s_{sa_i})\)。上面保存下来的所有长度为\(2^j\)的前缀的排名可以当哈希值来用（考场上我写了哈希）。然后用st表来维护区间最小值。现在我们可以\(O(1)\)求出\(LCP(s_u,s_v)\)了

　　考虑以\(x\)为根的子树，若\(u,v\)在\(x\)的不同子树内，则\(LCS(s_u,s_v)=d_x-1\)。这里\(d_x\)为点\(x\)的深度，根的深度为1。

　　因为\(LCP(s_{sa_{i-1}},s_{sa_i})\geq LCP(s_{sa_x},s_{sa_y})~(x\leq i-1<i\leq y)\)，所以我们只用求出以\(rk_i\)为关键字排序后相邻两个点的\(LCP\)。这个可以用线段树维护。然后线段树合并即可。

　　时间复杂度：\(O(n\log n)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

struct list

{

	int v[200010];

	int t[200010];

	int w[200010];

	int h[200010];

	int n;

	list()

	{

		n=0;

		memset(h,0,sizeof h);

	}

	void clear()

	{

		n=0;

		memset(h,0,sizeof h);

	}

	void add(int x,int y,int z)

	{

		n++;

		v[n]=y;

		t[n]=h[x];

		w[n]=z;

		h[x]=n;

	}

};

list l,l2;

int f[200010][20];

ll hs[200010][20];

int d[200010];

int e[200010];

int sa[200010];

int rk[200010];

int sx[200010];

int sy[200010];

int b[200010];

ll mod=1000000007;

ll pw[200010];

int ht[200010];

int st[200010][20];

int lo[200010];

int rt[200010];

int n;

int getmin(int x,int y)

{

	int t=lo[y-x+1];

	return min(st[x][t],st[y-(1<<t)+1][t]);

}

int query(int x,int y)

{

//	x=rk[x];

//	y=rk[y];

	if(x==y)

		return 0x3fffffff;

	if(x>y)

		swap(x,y);

	return getmin(x+1,y);

}

namespace seg

{

	struct p

	{

		int s,first,last,sz;

		p()

		{

			s=first=last=sz=0;

		}

	};

	int cnt;

	int ls[4000010];

	int rs[4000010];

	p s[4000010];

	void init()

	{

		memset(ls,0,sizeof ls);

		memset(rs,0,sizeof rs);

		cnt=0;

	}

	p mt(p a,p b)

	{

		if(!a.sz)

			return b;

		if(!b.sz)

			return a;

		p c;

		c.sz=a.sz+b.sz;

		c.first=a.first;

		c.last=b.last;

		c.s=max(max(a.s,b.s),query(a.last,b.first));

		return c;

	}

	int insert(int p,int x,int l,int r)

	{

		if(!p)

			p=++cnt;

		if(l==r)

		{

			s[p].sz=1;

			s[p].first=s[p].last=x;

			return p;

		}

		int mid=(l+r)>>1;

		if(x<=mid)

			ls[p]=insert(ls[p],x,l,mid);

		else

			rs[p]=insert(rs[p],x,mid+1,r);

		s[p]=mt(s[ls[p]],s[rs[p]]);

		return p;

	}

	int merge(int x,int y)

	{

		if(!x||!y)

			return x+y;

		ls[x]=merge(ls[x],ls[y]);

		rs[x]=merge(rs[x],rs[y]);

		s[x]=mt(s[ls[x]],s[rs[x]]);

		return x;

	}

};

int ans=0;

void solve(int x)

{

	rt[x]=seg::insert(rt[x],rk[x],1,n);

	int i;

	for(i=l.h[x];i;i=l.t[i])

	{

		solve(l.v[i]);

		rt[x]=seg::merge(rt[x],rt[l.v[i]]);

	}

	if(seg::s[rt[x]].sz>1)

		ans=max(ans,d[x]-1+seg::s[rt[x]].s);

}

int main()

{

	memset(rt,0,sizeof rt);

	seg::init();

	int i,j,x,y;

	pw[0]=311;

	for(i=1;i<=50;i++)

		pw[i]=pw[i-1]*pw[i-1]%mod;

	freopen("recollection.in","r",stdin);

	freopen("recollection.out","w",stdout);

	memset(f,0,sizeof f);

	scanf("%d",&n);

	d[1]=1;

	e[1]=310;

	hs[1][0]=310;

	for(i=2;i<=n;i++)

	{

		scanf("%d%d",&x,&y);

		l.add(x,i,y);

		f[i][0]=x;

		d[i]=d[x]+1;

		e[i]=y+1;

		hs[i][0]=e[i];

		for(j=1;j<=18;j++)

		{

			f[i][j]=f[f[i][j-1]][j-1];

			hs[i][j]=(hs[f[i][j-1]][j-1]*pw[j-1]+hs[i][j-1])%mod;

		}

	}

	int sz=310,k,o;

	for(i=1;i<=sz;i++)

		b[i]=0;

	for(i=1;i<=n;i++)

		b[sx[i]=e[i]]++;

	for(i=2;i<=sz;i++)

		b[i]+=b[i-1];

	for(i=n;i>=1;i--)

		sa[b[sx[i]]--]=i;

	for(j=1;(1<<j)<=n;j++)

	{

		l2.clear();

		k=0;

		for(i=1;i<=n;i++)

			if(d[sa[i]]>(1<<(j-1)))

				l2.add(f[sa[i]][j-1],sa[i],0);

		for(i=1;i<=n;i++)

			for(o=l2.h[sa[i]];o;o=l2.t[o])

				sy[++k]=l2.v[o];

		for(i=1;i<=n;i++)

			if(d[i]<=(1<<(j-1)))

				sy[++k]=i;

		for(i=1;i<=sz;i++)

			b[i]=0;

		for(i=1;i<=n;i++)

			b[sx[sy[i]]]++;

		for(i=2;i<=sz;i++)

			b[i]+=b[i-1];

		for(i=n;i>=1;i--)

			sa[b[sx[sy[i]]]--]=sy[i];

		k=0;

		swap(sx,sy);

		for(i=1;i<=n;i++)

			if(i!=1&&sy[sa[i]]==sy[sa[i-1]]&&((d[sa[i]]<=(1<<(j-1))&&d[sa[i-1]]<=(1<<(j-1)))||(d[sa[i]]>(1<<(j-1))&&d[sa[i-1]]>(1<<(j-1))&&sy[f[sa[i]][j-1]]==sy[f[sa[i-1]][j-1]])))

				sx[sa[i]]=k;

			else

				sx[sa[i]]=++k;

		if(k>=n)

			break;

		sz=k;

	}

	for(i=1;i<=n;i++)

		rk[sa[i]]=i;

	ht[0]=0;

	for(i=2;i<=n;i++)

	{

		x=sa[i-1];

		y=sa[i];

		int now=0;

		for(j=18;j>=0;j--)

			if(d[x]-1>=(1<<j)&&d[y]-1>=(1<<j)&&hs[x][j]==hs[y][j])

			{

				now+=(1<<j);

				x=f[x][j];

				y=f[y][j];

			}

		ht[i]=now;

	}

	for(i=1;i<=n;i++)

		st[i][0]=ht[i];

	for(j=1;j<=18;j++)

		for(i=1;i+(1<<j)-1<=n;i++)

			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);

	lo[1]=0;

	for(i=2;i<=n;i++)

		lo[i]=lo[i/2]+1;

	solve(1);

	printf("%d\n",ans);

	return 0;

}