原题链接

按着合并过程建树，按 $\text{dfs}$ 序重新排布字符串，那么每次查询就能用 $\text{dfs}$ 序拍成：新字符串的区间本质不同回文子串个数。

下面我们着手解决这个强化版问题。

::::success[区间本质不同回文子串个数]

根号分治或莫队做法就不提了，下面写写自己弄出来的 $\mathrm{polylog}$ 做法（应该和市面上的差不多吧？）。

按右端点离线，那么我们希望每个左端点 $i$ 贡献的恰为以 $i$ 为左端点的目前最长回文串。（“目前”指的是在当前处理的右端点 $R$ 左侧）

于是能发现每个左端点要么有贡献，要么没贡献，这就能涵盖所有回文串了。

现在我们考虑加入一个右端点 $R$，那么受影响的左端点 $L$ 肯定要满足 $S_{L\cdots R}$ 回文。

（上图中，红蓝粉色段都表示一个回文串，红串是不断由蓝串拼上相同循环节得出的，那么蓝串会是该循环节的一个前缀，比如红串可以是 $baabaab,baab$，而蓝串是 $b$。当前仅考虑这一段等差数列，对其他的等差段是同样处理的。）

可以看出，原先粉串的左端点的贡献可以直接继承，只不过贡献成了更长的红串，这种情况下我们啥都不用做（这也确实是大部分情况）。

（最上方的蓝粉紫三串是本质相同的。）

由于紫串的出现，粉串左端点原先不贡献。然而由于 $R$ 的加入，粉串左端点应该重新给红串算贡献；而紫串左端点也不应再贡献，而是要让蓝串左端点来贡献。

所以这时只需：删掉紫串左端点，加入粉串左端点。（蓝串在上一级的等差段中会算到贡献）

那么这种情况会不会发生在相邻两个红串之间呢？

由于蓝粉紫三串不交（否则相邻红蓝串间还有回文串），所以这种情况发生时至少得要有三倍以上的长度关系。而等差数列 $a_i=id+a,a\leq d(i\geq 1)$ 的相邻项比值至多是 $2$，所以不会发生。

还有一个同类的小情况：

上面的蓝串是以 $R$ 为右端点的最长串，蓝紫串本质相同。

这时仅需把紫串左端点给扬了即可。

（说这个情况和上面同类是因为你可以想象原串左侧有个镜像，于是能归到上面情况中。）

考虑具体实现。其实真正要做的事无非是：找某个串的最远出现位置（用以区分要删的紫串是否存在了）。

那么建完 $\text{PAM}$ 只需对后缀链接查个子树最大值，简单一个 $\text{Segment tree}$ 带走。

这部分每次跳等差段都去求的话是 $O(n\log ^2 n )$，但是能砍掉一个 $\log$。

其实在图二的情况中，蓝串必然是红串的后缀链接，而红串相同时结果必然相同，所以我们只用求 $O(n)$ 次子树最大值并记下来，这样就能 $O(n\log n)$。

可是影响到的端点数仍是能达到 $O(n\log n)$ 的（不过常数极小，$\log$ 以 $3$ 为底，还卡不满，个人只会用 $\texttt{a|bc|a|cb|a}{\Large\mid}\texttt{cd}{\Large\mid}\texttt{a|bc|a|cb|a}{\Large\mid}\texttt{dc}{\Large\mid}\texttt{a|bc|a|cb|a}\dots$ 来造上界，怀疑这里所谓的 $O(n)$ 就是错把这个 $\log$ 认为是常数了）。

假设用 $O(U_n)-O(Q_n)$ 单点修改，区间查询的数据结构，复杂度是 $O(n\log n \times U_n+q\times Q_n)$。

用 $\text{BIT}$ 可以跑出 $O(n\log ^2n+q\log n)$，当然 $n,q$ 同阶时可以多叉树平衡至 $O(n\log ^2 n/\log\log n)$。

::::

或者看这里。

这题数据弱，双 $\log$ 根本跑不近，于是成功最优解（

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int bufn1_max=1<<21;char buf1[bufn1_max];int bufn1;
const int bufn2_max=1<<21;char buf2[bufn2_max];int bufn2;
inline void flush_in(){fread(buf1,1,bufn1_max,stdin),bufn1=0;}
inline void flush_out(){fwrite(buf2,1,bufn2,stdout),bufn2=0;}
inline void gc(char &ch){
	if(bufn1==bufn1_max)flush_in();
	ch=buf1[bufn1++];
}
inline void pc(const char c){
	if(bufn2==bufn2_max)flush_out();
	buf2[bufn2++]=c;
}
char ch;bool read_flag;
template<typename T> inline void read(T &x){
	x=0;do{gc(ch);}while(!isdigit(ch));
	while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),gc(ch);
}
inline void write(int x){
	static int xx,nb,bit[10];nb=0;
	do{xx=x/10;bit[++nb]=x-(xx<<1)-(xx<<3);x=xx;}while(x);
	for(;nb;nb--)pc(48|bit[nb]);
}
inline void writesp(int x){write(x);pc(' ');}
inline void writeln(int x){write(x);pc('\n');}
const int N=1e5+10;
int n;bool aa[N];
bool a[N];
int lnk[N],top[N],d[N],tot,lst,x,y,yy,tmp;
int tr[N][2],mxlen[N],rev[N],dfn[N],dfnr[N],h[N],nxt[N];
void extend(int i,int c){
	y=lst;
	if(mxlen[y]==i-1)y=lnk[y];
	for(;a[i-mxlen[y]-1]!=c;y=lnk[y]);
	if(tr[y][c])tmp=tr[y][c];
	else {
		tmp=++tot,mxlen[tmp]=mxlen[y]+2;
		for(yy=y;y=lnk[y],a[i-mxlen[y]-1]!=c;);
		lnk[tmp]=tr[y][c]?tr[y][c]:2;
		tr[yy][c]=tmp;y=lnk[tmp];
		d[tmp]=mxlen[tmp]-mxlen[y];
		top[tmp]=(d[tmp]!=d[y])?tmp:top[y];
	}
	lst=tmp;
}
int st[N<<1];
void Dfs(){
	int sn,x,y,tt=0;
	st[sn=1]=1;
	while(sn){
		if((x=st[sn--])<0)dfnr[-x]=tt;
		else for(st[++sn]=-x,dfn[x]=++tt,
			y=h[x];y;y=nxt[y])st[++sn]=y;
	}
}
struct SGT{
	int mx[N<<2],k,l,r,mid,L,R,res;
	inline void cmax(int &x,int y){if(y>x)x=y;}
	inline void upd(int pos,int i){
		l=1,r=tot,mx[k=1]=i;
		while(l!=r){
			mid=l+r>>1,k<<=1;
			pos>mid?k|=1,l=mid+1:r=mid;
			mx[k]=i;
		}
	}
	void inq(int k,int l,int r){
		if(L<=l&&r<=R)cmax(res,mx[k]);
		else {
			int mid=(l+r)>>1;
			if(L<=mid)inq(k<<1,l,mid);
			if(mid<R)inq(k<<1|1,mid+1,r);
		}
	}
	int inq(int l,int r){res=0,L=l,R=r,inq(1,1,tot);return res;}
}S;
#define lowbit(i) i&(-i)
struct Bit{
	int t[N],r;
	inline void upd(int i){for(;i;i-=lowbit(i))++t[i];}
	inline void del(int i){for(;i;i-=lowbit(i))--t[i];}
	inline int inq(int i){for(r=0;i<=n;i+=lowbit(i))r+=t[i];return r;}
}T;
int s[N];bool bs[N];
void Upd(int i){
	static int x,y,lst;
	x=rev[i];
	if(mxlen[x]<(i>>1)){
		lst=S.inq(dfn[x],dfnr[x]);
		if(lst)T.del(lst-mxlen[x]+1);
	}
	while(y=top[x],(x=lnk[y])>2)
	if(mxlen[x]*3+2<mxlen[y]){
		if(!bs[y]){
			s[y]=i-S.inq(dfn[x],dfnr[x])+mxlen[x];
			if(s[y]>=mxlen[y])s[y]=0;bs[y]=1;
		}
		if(s[y])T.del(i-s[y]+1),T.upd(i-mxlen[y]+1);
	}
}
int f[N<<1],ans[N];
inline int getf(int x){while(x!=f[x])x=f[x]=f[f[x]];return x;}
int son[N<<1][2],hq[N],nxtq[N],L[N];
void dfs(int Rt){
	int sn,x,nn=0;
	st[sn=1]=Rt;
	while(sn){
		if((x=st[sn--])<0)nxtq[-n-x]=hq[nn],hq[nn]=-n-x;
		else if(x>n){
			st[++sn]=-x,L[x-n]=nn+1;
			if(son[x][1])st[++sn]=son[x][1];
			if(son[x][0])st[++sn]=son[x][0];
		}
		else a[++nn]=aa[x];
	}
}
void main_(){
	read(n);int i,x,y,xf,yf;
	do{gc(ch);}while(ch<33);
	for(i=1;i<=n;++i)aa[i]=ch&1,gc(ch);
	for(i=(n<<1)-1;i;--i)f[i]=i;
	for(i=1;i!=n;++i){
		read(x),read(y),x=getf(x),y=getf(y);
		f[son[n+i][0]=x]=f[son[n+i][1]=y]=n+i;
	}
	dfs((n<<1)-1);
	mxlen[1]=-1,mxlen[2]=0,tot=2,lst=1;
	top[1]=1,top[2]=2,lnk[1]=lnk[2]=1,d[1]=d[2]=-1;
	for(i=1;i<=n;++i)extend(i,a[i]),rev[i]=tmp;
	for(i=2;i<=tot;++i)nxt[i]=h[lnk[i]],h[lnk[i]]=i;
	Dfs();
	for(x=1;x<=n;++x){
		Upd(x);S.upd(dfn[rev[x]],x),T.upd(x);
		for(i=hq[x];i;i=nxtq[i])L[i]=T.inq(L[i]); 
	}
	for(i=1;i!=n;++i)writeln(L[i]);
}
int main(){
	flush_in();
	main_();
	flush_out();
}