CF1006E Military Problem 题解

题意

给定一颗有 \(n \thinspace (2 \leq n \leq 2 \times 10^5)\) 个节点的树，树根为 \(1\)。

对于每个节点 \(i \thinspace (2 \leq i \leq n)\) 都有它的父节点 \(p_i\)，并且每个节点的子节点都是按从小到大的顺序排列的的。

有 \(q \thinspace (1 \leq q \leq 2 \times 10^5)\) 个询问，每次询问都有一个 \(u_i,k_i \thinspace (1 \leq u_i,k_i \leq n)\)，输出以 \(u_i\) 为根的子树的前序遍历中排名为 \(k_i\) 的元素。

如果子树中没有 \(k_i\) 个节点则输出 \(-1\)。

暴力做法

对于每个询问 \(i\) 的 \(u_i\)，直接在以 \(u_i\) 为根的子树中做前序遍历，取第 \(k_i\) 个被遍历到的元素作为答案即可。

由于每次遍历都有可能遍历整棵树，所以时间复杂度最坏为 \(O(nq)\)，会超时。

正解

继续在暴力做法上寻找优化方法。

如果我们画图会发现，一棵子树内前序遍历的编号是连续的。

所以我们就可以利用这一性质，在树的前序遍历上做询问。

先对整棵树跑一边前序遍历并将其记录下来。

在询问时，先找到 \(u_i\) 在前序遍历中的下标 \(o\)，再找寻前序遍历中以下标 \(o\) 开始的第 \(k_i\) 元素的下标 \(l\)。

最终前序遍历中下标为 \(l\) 的元素即为所求答案。

对于输出 \(-1\) 的情况，只需要记录一下以 \(i \thinspace (1 \leq i \leq n)\) 为根的子树大小 \(size_i\)。在询问时，判断是否 \(size_{u_i} < k_i\) 即可。

由于预处理时间复杂度为 \(O(n)\)，每次询问时间复杂度为 \(O(1)\)，所以最终时间复杂度为 \(O(n+q)\)，可以通过测试。

代码

#include<stdio.h>
#include<vector>
const int N=2e5+5;
std::vector<int> v[N];
int n,m,num[N],cnt,kth[N],size[N];
void build(int u){//预处理
	num[++cnt]=u;//前序遍历编号对应元素
	kth[u]=cnt;//元素对应编号
	size[u]=1;//子树大小
	for(auto son:v[u]) build(son),size[u]+=size[son];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2,x;i<=n;i++) scanf("%d",&x),v[x].emplace_back(i);
	build(1);
	int x,y;
	while(m--){
		scanf("%d%d",&x,&y);
		if(size[x]<y) puts("-1");
		else printf("%d\n",num[kth[x]+y-1]);
	}
	return 0;
}