自动搬运

查看原文

来自洛谷，原作者为

	耳朵龙_ 老师说不要看没用的东西，看来不能照镜子了

搬运于2025-08-24 22:58:58，当前版本为作者最后更新于2024-05-25 18:11:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

与字符集大小无关的 $O(n\log n)$ 做法，狠狠爆标！场上写的是时空 $O(n|\Sigma|)$ 的长剖做法。

若字符集较大可以先离散化，下面认为字符集大小为 $O(n)$。记 $f_{i,j}$ 表示从 $i$ 开始，走到 $i$ 子树内任意一个叶子，能选出的开头为 $j$ 的最长不降子序列长度（忽略 $p_i$ 的限制）。枚举是否选择点 $i$，再枚举走向的子结点 $u$，有转移

$$f_{i,j}=\begin{cases}1+\max\limits_{v= c_i}^{|\Sigma|}\max\limits_uf_{u,v}&j=c_i\\\max\limits_uf_{u,j}&j\ne c_i\end{cases} $$

用线段树合并维护第二维，可以 $O(n\log n)$ 求出所有 $f$ 值。设 $g_i=\max_{j=1}^{|\Sigma|}f_{i,j}$。设 $h_i=f_{i,c_i}$，即必须选择 $i$ 时的最长不降子序列长度。设点 $i$ 的答案为 $ans_i$，深度为 $d_i$，其子树内结点的集合为 $S_i$。

求答案时，设 $a_i$ 表示选择点 $i$ 的符合题意的最长不降子序列长， $b_i$ 表示不选择点 $i$ 的符合题意的最长不降子序列长，则 $ans_i=\max(a_i,b_i)$。将这两部分分开考虑。

枚举子序列的第一个点，有

$$b_i=\max_{u\in S_i,d_u\ge d_i+p_i}h_u=\max_{u\in S_i,d_u\ge d_i+p_i}g_u $$

对于互为父子的点 $x,y$，有 $g_x\ge g_y$，因此，

$$b_i=\max_{u\in S_i,d_u=d_i+p_i}g_u$$

设 $s_{i,k}$ 表示 $i$ 子树内所有深度为 $k$ 的结点 $u$ 其 $g_u$ 的最大值，$b_i$ 即为 $s_{i,d_i+p_i}$。$s$ 的维护是长链剖分的基本操作，不再赘述，计算出 $g$ 后，这一部分的总时间复杂度为 $O(n)$。

注意到 $a_i\le b_i+1$，因此，$ans_i=a_i>b_i$ 当且仅当 $a_i=b_i+1$。也就是说，我们通过求出 $b$，绕过了困难（我不会）的求 $a$，转而解决简单的判定 $a_i$ 是否等于 $b_i+1$ 的问题。枚举子序列的第二个点，有

$$a_i=1+\max_{u\in S_i,d_u\ge d_i+p_i,c_u\ge c_i}h_u $$

因此只需判断是否有

$$b_i=\max_{u\in S_i,d_u\ge d_i+p_i,c_u\ge c_i}h_u$$

即可求出 $ans_i$。变形一下，上式即为判断是否有

$$d_i+p_i\le\max_{u\in S_i,h_u=b_i,c_u\ge c_i}d_u$$

开 $\max_ih_i=O(n)$ 棵动态开点线段树，将所有点按照 $c$ 从大到小排序，插入点 $i$ 时令第 $h_i$ 棵线段树 $dfn_i$ 处的值对 $d_i$ 取 $\max$，查询 $i$ 时判断其子树 $dfn$ 区间内最大值是否不小于 $d_i+p_i$ 即可。这一部分的总时间复杂度为 $O(n\log n)$。

总时空复杂度均为 $O(n\log n)$。这题字符集很小，代码里没有实现离散化：

#include<bits/stdc++.h>
namespace IO{
const int L=(1<<20)+30;
char buf[L],*s,*t,pbuf[L],*p=pbuf;
#define gf() (s==t&&(s=buf)==(t=buf+fread(buf,1,L,stdin))?-1:*s++)
void rd(int&x){
	x=0;char c=gf();
	while(c<48) c=gf();
	while(c>=48) x=x*10+(c^48),c=gf();
}
void rd(char*x){
	do *x=gf();while(*x<48);
	while(*x>=48) *x-='a'-1,*++x=gf();
	*x=0;
}
void fl(){fwrite(pbuf,1,p-pbuf,stdout),p=pbuf;}
void pf(char c){if(p-pbuf==L) fl();*p++=c;}
void wt(int x){
	static int st[30],tp;
	do st[++tp]=x%10,x/=10;while(x);
	while(tp) pf(st[tp--]|48);
	pf(10);
}
}
using IO::rd;
using IO::wt;
using namespace std;
const int N=100005;
int n,m=26,maxr,p[N],dep[N],ans[N],dfn[N],sz[N],tim,len[N],son[N],s[N],h[N],rt[N],idx;
struct tn{int Ls,Rs,v;}tr[N*18];
#define ls tr[u].Ls
#define rs tr[u].Rs
vector<int>E[N],F[N];
char c[N];
int query(int u,int L,int R,int l=1,int r=maxr){
	if(!u||(L<=l&&r<=R)) return tr[u].v;
	int mid=(l+r)/2,z=0;
	if(L<=mid) z=query(ls,L,R,l,mid);
	if(R>mid) z=max(z,query(rs,L,R,mid+1,r));
	return z;
}
void insert(int&u,int x,int v,int l=1,int r=maxr){
	if(!u) tr[u=++idx]={0,0,0};
	if(tr[u].v=max(tr[u].v,v),l<r){
		int mid=(l+r)/2;
		x>mid?insert(rs,x,v,mid+1,r):insert(ls,x,v,l,mid);
	}
}
int merge(int u,int v){
	if(!u||!v) return u^v;
	ls=merge(ls,tr[v].Ls),rs=merge(rs,tr[v].Rs);
	return tr[u].v=max(tr[u].v,tr[v].v),u;
}
void getdep(int x,int pr){
	sz[x]=1;
	for(int y:E[x])
		if(y^pr){
			dep[y]=dep[x]+1,getdep(y,x),sz[x]+=sz[y];
			if(len[y]>len[son[x]]) son[x]=y;
		}
	len[x]=son[x]?len[son[x]]:dep[x];
}
void dfs(int x,int pr){
	dfn[x]=++tim;
	if(son[x]) dfs(son[x],x),rt[x]=rt[son[x]];
	for(int y:E[x])
		if(y^pr&&y^son[x]){
			dfs(y,x),rt[x]=merge(rt[x],rt[y]);
			for(int i=dep[y];i<=len[y];++i)
				s[dfn[x]+i-dep[y]+1]=max(s[dfn[x]+i-dep[y]+1],s[dfn[y]+i-dep[y]]);
		}
	h[x]=1+query(rt[x],c[x],m);
	insert(rt[x],c[x],h[x]),s[dfn[x]]=tr[rt[x]].v;
	ans[x]=len[x]<dep[x]+p[x]?1:s[dfn[x]+p[x]];
	F[int(c[x])].emplace_back(x);
}
#define eb emplace_back
int main(){
	rd(n);
	for(int i=1;i<=n;++i) rd(p[i]);
	rd(c+1);
	for(int i=1,u,v;i<n;++i)
		rd(u),rd(v),E[u].eb(v),E[v].eb(u);
	getdep(1,1),maxr=m,dfs(1,1),idx=0,maxr=n;
	for(int i=1;i<=n;++i) rt[i]=0;
	for(int i=m;i;--i){
		for(int x:F[i]) insert(rt[h[x]],dfn[x],dep[x]);
		for(int x:F[i])
			if(sz[x]>1)
				ans[x]+=query(rt[ans[x]],dfn[x]+1,dfn[x]+sz[x]-1)>=dep[x]+p[x];
	}
	for(int i=1;i<=n;++i) wt(ans[i]);
	return IO::fl(),0;
}