题解 P10536 [Opoi 2024] 二十六点

· · 题解

与字符集大小无关的 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;
}