自动搬运

查看原文

来自洛谷，原作者为

	wuhao2005 **

搬运于2025-08-24 22:30:38，当前版本为作者最后更新于2021-04-12 09:20:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题面：

题目链接

题解：

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

我们考虑对给进来的 $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;
}