本文主要是介绍acwing 4310. 树的DFS，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • dfs算法求解
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

给定一棵 nn 个节点的树。

节点的编号为 1∼n1∼n，其中 11 号节点为根节点，每个节点的编号都大于其父节点的编号。

现在，你需要回答 qq 个询问。

每个询问给定两个整数 ui,kiui,ki。

我们希望你用 DFS（深度优先搜索）算法来遍历根节点为 uiui 的子树。

我们规定，当遍历（或回溯）到某一节点时，下一个遍历的目标应该是它的未经遍历的子节点中编号最小的那一个子节点。

例如，上图实例中：

• 如果遍历根节点为 11 号节点的子树，则子树内各节点的遍历顺序为 [1,2,3,5,6,8,7,9,4][1,2,3,5,6,8,7,9,4]。
• 如果遍历根节点为 33 号节点的子树，则子树内各节点的遍历顺序为 [3,5,6,8,7,9][3,5,6,8,7,9]。
• 如果遍历根节点为 77 号节点的子树，则子树内各节点的遍历顺序为 [7,9][7,9]。
• 如果遍历根节点为 99 号节点的子树，则子树内各节点的遍历顺序为 [9][9]。

每个询问就是让你计算采用规定的 DFS 算法来遍历根节点为 uiui 的子树时，第 kiki 个被遍历到的节点的编号。

输入格式

第一行包含两个整数 n,qn,q。

第二行包含 n−1n−1 个整数 p2,p3,…,pnp2,p3,…,pn，其中 pipi 表示第 ii 号节点的父节点的编号。

接下来 qq 行，每行包含两个整数 ui,kiui,ki，表示一组询问。

输出格式

共 qq 行，每组询问输出一行一个整数表示第 kiki 个被遍历到的节点的编号。

如果第 kiki 个被遍历到的节点不存在，则输出 −1−1。

数据范围

前三个测试点满足 2≤n≤202≤n≤20，1≤q≤201≤q≤20。
所有测试点满足 2≤n≤2×1052≤n≤2×105，1≤q≤2×1051≤q≤2×105，1≤pi<i1≤pi<i，1≤ui,ki≤n1≤ui,ki≤n。

输入样例：

9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9

输出样例：

3
6
8
-1
9
4

dfs算法求解

分析

首先使用dfs，用path数组记录整个dfs的遍历顺序，（注意对于节点u的每个节点，要按编号从小到大遍历）

遍历过程中记录每个以u为根的子树的大小cnt[u]（包括u本身）

然后用一个数组order记录某个节点u在path中的下标

对于每个询问，u，k

• 首先看k的大小是否超过了以u为根的子树大小
  • 超过输出-1
  • 不超过的话，首先用order[u]找到u在path中的下标，然后往后数k-1个就是目标节点

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
#include<cmath>
using namespace std;
const int N = 200010;
vector<int> h[N];
vector<int> path;
int n, q;

int order[N];
int cnt[N]; // cnt[i]表示以i为根的子树的大小 

int k;

int dfs(int u)
{
	path.push_back(u);
	
	cnt[u] = 1; // u本身是该子树的一个节点
	for(int i = 0; i < h[u].size(); i++)
	{
		int j = h[u][i];
		cnt[u] += dfs(j);
	}
	return cnt[u];
}
int main()
{
	scanf("%d%d", &n, &q);
	for(int i = 2; i <= n; i++) 
	{
	    int a;
		scanf("%d", &a);
		h[a].push_back(i);
	}
	for(int i = 1; i <= n; i++) sort(h[i].begin(), h[i].end());
	
 	path.push_back(0);
	dfs(1);
	
//	for(int i = 1; i < path.size(); i++) cout << path[i] << " ";
//	return 0;
	
	for(int i = 1; i < path.size(); i++)  order[path[i]] = i; // 记录path[i]在遍历顺序中的下标
	
	while(q --)
	{
	    int u, k;
	    scanf("%d%d", &u, &k);
	    if(k <= cnt[u]) printf("%d\n",path[order[u] + k - 1]); // order[u]表示u在path[]中的下标
	    else            printf("-1\n");
	}
	return 0;
}

时间复杂度

\(O(n)\)

参考文章

https://www.acwing.com/file_system/file/content/whole/index/content/4147870/

这篇关于acwing 4310. 树的DFS的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！