[省选联考 2021 A/B 卷] 宝石

· · 题解

题面：

题目链接

题解：

提供赛时思路，比较清真，只要主席树加倍增就行了

我们考虑对给进来的 P_i 重标号一下，使之成为 1\sim c 的序列，同时对每个 i 的 w 值也进行对应的重标

那么题意可以转化为求一条路径上 u\rightarrow v 的最大的 cnt ，满足 cnt\le c 且 1\sim cnt 在这条路径上依次出现

显然在这条路径上，每个权值尽量早的出现最优

对于一条路径，可以拆分一条上链和一条下链

那么我们对于每个点 u 可以倍增预处理 f_1[u][i] 表示在 u 到根的链上权值为 w[u]+2^i 的节点最近在哪里

和 f_2[u][i] 表示在 u 到根的链上权值为 w[u]-2^i 的节点最近在哪里（为了处理下链）

对于上链可以直接求出权值为 1 的节点在哪里（因为必须从 1 开始起跳，怎么查找从 u 到根的链上权值为 x 的节点待会讲），并从 1 开始起跳，一直跳到深度不小于 lca 的节点

这样我们就得到了上链最大能匹配到哪里，不妨设为 x

那么我们可以在下链上二分答案，下界为 x+1 ，上界为 c，在 v 到根的链上查找权值为 mid 的点，并利用 f_2 不断往上跳，找到最大能匹配的后缀，看看是否能和前 1\sim x 拼接在一起

（答案显然具有单调性的，因为如果权值较大的点能和上链拼接在一起，那么权值较小的点更加可以和上链拼在一起了）

至于二分的下界是 x+1 的原因是 x 是在上链上出现的，不保证在下链上也存在 x

至于如何在线求一条到根的链上权值为 p 的点最深在哪里可以主席树一下，就是每个孩子在他父亲的线段树上更改一条链就行了（可能有点表述不清，可以看代码）

复杂度 O(n\log^2n) ，常数可能有点大，因为倍增的 \log 是要跑满的，不过应该能过题

说句题外话，考试的时候没注意到二分的下界是 x+1 ，导致代码出错了

其实如果测最大的那个样例应该是可以测出来的，但是我不会手动开大 Windows 的栈空间，一个 dfs 就跑不出来，还以为思路错了，想了半天

这里记录下 Windows 下手动开大栈空间的方法

在 dev 的工具那一栏的编译选项，在“编译时加入以下命令”那个地方加上

-Wl,--stack=1024000000

所有局部变量和函数都是算在栈空间内的，上面那个 = 号后面的东西是以 B 为单位的

一般来说是递归深度过大导致爆栈的

和 Ubuntu 的

编译前在终端加上 ulimit -s 1024000

这个是以 KB 为单位的

Code：

#include<bits/stdc++.h>
using namespace std;
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
const int N = 2e5+9;
int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return f*x;
}

int n,m,c,q,p[N],w[N],vt[N];
int head[N],tot;
struct pp{int nxt,to;}g[N<<1];
void add(int u,int v){g[++tot].nxt=head[u],g[tot].to=v,head[u]=tot;}
int pa[N],dep[N],f[N][21];

void dfs1(int u,int fa){
    pa[u]=fa,dep[u]=dep[fa]+1,f[u][0]=fa;
    for(int i=head[u];i!=-1;i=g[i].nxt){
        int v=g[i].to;if(v==fa) continue;dfs1(v,u);
    }
    return ;
}

int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=20;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return f[u][0];
}

int col[N];
int f1[N][21],f2[N][21];
void dfs2(int u,int fa){
    int hy=col[w[u]];
    col[w[u]]=u;
    f1[u][0]=col[w[u]+1],f2[u][0]=col[w[u]-1];
    for(int i=head[u];i!=-1;i=g[i].nxt){
        int v=g[i].to;if(v==fa) continue;dfs2(v,u);
    }
    col[w[u]]=hy;
    return ;
}

int rt[N],cnt;
struct seg{int ch[2],pos;}t[N*64];
int New(){++cnt;ls(cnt)=rs(cnt)=0,t[cnt].pos=0;return cnt;}
void modify(int &c,int pt,int l,int r,int x,int y){
    if(!c) c=New();if(l==r){t[c].pos=y;return ;}int mid=(l+r)>>1;
    if(x<=mid) rs(c)=rs(pt),modify(ls(c),ls(pt),l,mid,x,y);
    if(x>mid) ls(c)=ls(pt),modify(rs(c),rs(pt),mid+1,r,x,y);return ;
}
int query(int c,int l,int r,int x){
    if(!c) return 0;if(l==r) return t[c].pos;
    int mid=(l+r)>>1;if(x<=mid) return query(ls(c),l,mid,x);
    if(x>mid) return query(rs(c),mid+1,r,x);
}

void dfs3(int u,int fa){
    modify(rt[u],rt[fa],1,n,w[u],u);
    for(int i=head[u];i!=-1;i=g[i].nxt){
        int v=g[i].to;if(v==fa) continue;dfs3(v,u);
    }   
    return ;
}

int jump(int u,int d){
    if(dep[u]<d) return 0;
    for(int i=20;i>=0;i--) if(dep[f1[u][i]]>=d) u=f1[u][i];
    return w[u];
}

int jump2(int u,int d){
    for(int i=20;i>=0;i--) if(dep[f2[u][i]]>=d) u=f2[u][i];
    return w[u];
}

int check(int v,int x,int d,int se){
    int u=query(rt[v],1,n,x);
    if(dep[u]<d) return 0;
    int st=jump2(u,d);
    return (st<=(se+1));
}

int main(){
    memset(head,-1,sizeof(head));tot=0;
    n=read(),m=read(),c=read();
    for(int i=1;i<=c;i++) p[i]=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<n;i++){int u=read(),v=read();add(u,v);add(v,u);}
    memset(vt,0,sizeof(vt));
    int kt=c;
    for(int i=1;i<=c;i++) vt[p[i]]=i;
    for(int i=1;i<=n;i++){if(!vt[w[i]]) vt[w[i]]=++kt;w[i]=vt[w[i]];}
    dfs1(1,0);
    for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    q=read();
    memset(rt,0,sizeof(rt));memset(col,0,sizeof(col));
    dfs2(1,0);
    for(int j=1;j<=20;j++) for(int i=1;i<=n;i++) f1[i][j]=f1[f1[i][j-1]][j-1],f2[i][j]=f2[f2[i][j-1]][j-1];
    cnt=0;dfs3(1,0);
    for(int i=1;i<=q;i++){
        int u=read(),v=read();int pt=lca(u,v);
        int fi=query(rt[u],1,n,1);
        int se=min(jump(fi,dep[pt]),c);
        int l=se+1,r=c,ans=se;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(v,mid,dep[pt],se)) l=mid+1,ans=mid;
            else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}