自动搬运

查看原文

来自洛谷，原作者为

	fzitb7912 worio，磨灭，依靠。

搬运于2025-08-24 23:13:28，当前版本为作者最后更新于2025-04-15 18:17:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

直接算吧。先把 $\operatorname{LCA}(l,l+1,\dots,r)$ 求出来，记为 $x$。然后分类讨论：

1. $l \le x \le r$。那么除开 $x$ 外剩下的点不存在 $\operatorname{LCA}(i,j)=i$。记 $y$ 为它们的 $\operatorname{LCA}$，那么 $y \ne x$。
2. $x < l\lor x>r$。那么这些点不存在 $\operatorname{LCA(i,j)}=i$。

所以现在问题变成了一个判定区间内是否存在一对点 $(i,j)$，使得其中一个是另一个的祖先。这个是个典的东西。我们对于每个点 $u$ 记录 $pre_u$ 表示 $u$ 子树中最大的满足 $v < u$ 的 $v$ 值，$nxt_u$ 表示 $u$ 子树中最小的满足 $v>u$ 的 $v$ 值。那么当 $[l,r]$ 中存在一个点 $i$，满足 $pre_i \ge l \lor nxt_i \le r$，就一定存在至少一对点了。预处理这个可以跑一遍 DFS。

求区间 $\operatorname{LCA}$ 是典 trick，区间中相邻两个 $\operatorname{LCA}$ 深度最小的就是区间的 $\operatorname{LCA}$。

但是这么做会有一点小问题。就是如果我们一共有 $2$ 个点，且它们相邻，我们并不会判定它们不行。为什么呢，因为我们只看了 $y \ne x$。而 $y \ne x$ 时我们决策的 $p$ 是在 $y$ 点上的。所以如果 $y$ 上面有点就错了。这个特殊处理即可。那为什么点数 $>2$ 时不会错呢，因为我们一定有 $y$ 子树内某个点 $z$ 属于区间 $[l,r]$，已经判掉了。

这样做的时间复杂度为 $O(n\log n+q)$，标程在写什么。

代码

il void dfs(int u,int fa){
	dep[u]=dep[fa]+1,
	f[u][0]=fa;
	for(re int i=1;i<20;++i) f[u][i]=f[f[u][i-1]][i-1];
	auto it=st.lower_bound(u);
	if(it!=st.begin()){
		--it;
		nxt[*it]=min(nxt[*it],u);
	}
	it=st.lower_bound(u);
	if(it!=st.end()){
		pre[*it]=max(pre[*it],u);
	}
	st.insert(u);
	for(auto v:e[u])
	if(v!=fa) dfs(v,u);
	st.erase(u);
	return ;
}
il int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(re int i=19;i>=0;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(re int i=19;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0]; 
}
il int query_lca(int l,int r){
	if(l>r) return l;
	int k=__[r-l+1];
	if(dep[lc[l][k]]<=dep[lc[r-(1ll<<k)+1][k]]) return lc[l][k];
	return lc[r-(1ll<<k)+1][k];
}
il int query_min(int l,int r){
	if(l>r) return inf;
	int k=__[r-l+1];
	return min(Min[l][k],Min[r-(1ll<<k)+1][k]);
}
il int query_max(int l,int r){
	if(l>r) return -inf;
	int k=__[r-l+1];
	return max(Max[l][k],Max[r-(1ll<<k)+1][k]);
}

il void solve(){
	n=rd,q=rd;
	for(re int i=1;i< n;++i){
		int u=rd,v=rd;
		e[u].push_back(v),
		e[v].push_back(u); 
	}
	for(re int i=1;i<=n;++i) pre[i]=-inf,nxt[i]=inf;
	dfs(1,0);
	for(re int i=0;i< N;++i) __[i]=log2(i);
	for(re int i=1;i<=n;++i){
		if(i<n) lc[i][0]=lca(i,i+1);
		Min[i][0]=nxt[i],
		Max[i][0]=pre[i];
	}
	for(re int j=1;j<20;++j)
	for(re int i=1;i+(1ll<<j)-1<=n;++i){
		if(dep[lc[i][j-1]]<=dep[lc[i+(1ll<<(j-1))][j-1]]) lc[i][j]=lc[i][j-1];
		else lc[i][j]=lc[i+(1ll<<(j-1))][j-1];
		Min[i][j]=min(Min[i][j-1],Min[i+(1ll<<(j-1))][j-1]),
		Max[i][j]=max(Max[i][j-1],Max[i+(1ll<<(j-1))][j-1]);
	}
	while(q--){
		int l=rd,r=rd;
		if(l==r){
			puts("Yes");
			continue;
		}
		int x=query_lca(l,r-1);
		if(x<l||x>r){
			int mx=query_max(l,r);
			int mi=query_min(l,r);
			if(mx>=l||mi<=r) puts("No");
			else puts("Yes");
		}
		else{
			int Lca;
			if(x==l) Lca=query_lca(l+1,r-1);
			else if(x==r) Lca=query_lca(l,r-2);
			else Lca=lca(query_lca(l,x-2),query_lca(x+1,r-1));
			if(Lca==x){
				puts("No");
				continue;
			}
			if(dep[Lca]==dep[x]+1&&r-l+1==2){
				puts("No");
				continue;
			}
			int mi=min(query_min(l,x-1),query_min(x+1,r));
			int mx=max(query_max(l,x-1),query_max(x+1,r));
			if(mi<=r||mx>=l) puts("No");
			else puts("Yes");
		}
	}
    return ;
}