自动搬运

查看原文

来自洛谷，原作者为

	Reply_ 我恨快速幂

搬运于2025-08-24 23:08:00，当前版本为作者最后更新于2025-08-13 20:33:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：P11513 [ROIR 2017] 培训 (Day 2)

类似于折跃点的，每个限制要求的点都在某棵子树的某一层，但这题更加简单。

65pts 做法

想找到所有限制的所有点，考虑到直接找不好找，我们 dfs 一遍记录所有点的 dfn 序以及所有子树的大小，每一层开一个 vector 记录这一层的点的 dfn 序。

我们想找到在某一层中找到属于某棵子树的点，利用 dfn 序就可以简单判断：对于子树 $u$，其子树的 dfn 序必定是连续的，且为 $dfn_u\sim dfn_u+siz_u-1$，那么当且仅当某一层的点的 dfn 序属于这个范围中时，该点便是在该层的属于子树 $u$ 的节点。

统计答案时，观察到当 $L$ 固定时，$R$ 越大越能满足要求。因此采用双指针统计答案区间即可。

具体讲，在 dfs 的时候，记录点的 dfn 序和深度，以及每个 dfn 序对应的点的编号，再在每个深度开一个 vector 记录这一层所有点的 dfn 序。统计每个限制的时候，利用二分找到在某一层的 vector 中，这个限制要求的点的区间。遍历这个区间的每个节点，每个节点再开一个 vector，记录哪几个限制包含了该点。

在统计答案时，保持左端点不动，右端点右移，加入该点贡献，直到满足所有限制为止。记录答案后再将左端点右移，减去该点贡献即可。

code

所有注释均为调试信息。

100pts 做法

观察每个限制的区间不难发现，不存在哪两个区间是交叉的，即所有的区间都是以大区间包含小区间的方式存在。

那么我们就没有必要考虑所有的限制区间，只考虑被包含的小的区间，小的区间满足了，包含它的大的区间一定满足，只统计这个区间的答案即可。

#include<bits/stdc++.h>
#define ll long long
#define R1 register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R1 int x=0,t=1;R1 char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=2e5+10;
vector<int>g[N];
int id1[N],tot,id2[N],b[N];
void add(int ui,int vi)
{
	g[ui].push_back(vi);
	return;
}
void bfs(int st)
{
	queue<int>q;
	q.push(st);
	while(q.size()){
		int u=q.front();
		id1[u]=++tot;
		q.pop();
		for(int v:g[u]){
			q.push(v);
		}
	}
	tot=0;
	return;
}
vector<int>d[N],f[N];
int dep[N],siz[N],sum[N];
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	siz[u]=1;
	id2[u]=++tot;
	b[tot]=u;
	d[dep[u]].push_back(id2[u]);
	for(int v:g[u]){
		dfs(v,u);
		siz[u]+=siz[v];
	}
	return;
}
struct node
{
	int l,r,k;
}q[N],q1[N];
bool cmp(node x,node y)
{
	if(x.k!=y.k) return x.k<y.k;
	if(x.l!=y.l) return x.l<y.l;
	return x.r<y.r;
}
signed main()
{
	int n=read();
	F(i,2,n){
		add(read(),i);
	}
	bfs(1);
	dfs(1,0);
	int m=read();
	F(i,1,m){
		int u=read(),k=read();
		k=dep[u]+k;
		int L=id2[u],R=id2[u]+siz[u]-1;
		int l=0,r=d[k].size()-1,ql=-1,qr=-1;
		while(l<=r)
		{
			int mid=l+r>>1;
			if(d[k][mid]<L){
				l=mid+1;
			}
			else r=mid-1,ql=mid;
		}
		l=0,r=d[k].size()-1;
		while(l<=r){
			int mid=l+r>>1;
			if(d[k][mid]>R) r=mid-1;
			else{
				l=mid+1;
				qr=mid;
			}
		}
		q[i].l=ql,q[i].r=qr,q[i].k=k;
	}
	sort(q+1,q+1+m,cmp);
	int tott=0;
	F(i,1,m){
		if(q[i].k!=q[i-1].k){
			q1[++tott]=q[i];
		}
		else{
			if(q[i].l!=q[i-1].l) q1[++tott]=q[i];
		}
	}
	m=tott;
	F(i,1,m){
		F(j,q1[i].l,q1[i].r){
			int tmp=b[d[q1[i].k][j]];
			f[tmp].push_back(i);
		}
	}
	
	int r=0,cnt=0;
	int minn=1e9,al,ar;
	for(int i = 1;i<=n;i++){
		while(r<n && cnt!=m){
			r++;
			for(int v:f[r]){
				if(sum[v]==0){
					cnt++;
				}
				sum[v]++;
			}
		}
		if(cnt!=m){
			break;
		}
		int len=r-i+1;
		if(len<minn){
			minn=len;
			al=i,ar=r;
		}
		for(int v:f[i]){
			if(sum[v]==1){
				cnt--;
			}
			sum[v]--;
		}
	}
	cout << al << " " << ar << '\n';
	return 0;
}
/*

*/