题意 你有一棵有个节点的树，有次询问，每次询问有，指从以为根的子树出发到达的第个点是哪一个？如果不存在（即，子树的大小小于），输出。 分析 很的一道题啊。你先预处理出每个点的序以及每个序对应的点和每棵子树的大小就可以了。询问的时候输出就好了。（数组存的是每个点的序，数组存的是每个序对应的点）. 代码
展开全文
题目大意：给你一棵树，然后有q个询问(u,k),问以u为根进行深度优先搜索第k个元素是多少？思路：朴素做法：对于q个询问，每个询问dfs一下求第k个元素即可。---超时正解：我们可以先求出以1为根的所有节点的dfs序，然后记录一下第i个dfs序是谁，然后对于q个询问输出第(dfn[u] + k -
展开全文
分析 题目要求求出当前点子树dfs遍历时第v个到达的点的编号那么我们可以直接走dfn序然后用一个数组记录那么每次只需要特判加输出即可时间复杂度：期望得分：100分 代码 //CF1006E
#include <algorithm>
#include <iostream>
#i
展开全文
Military Problem DFS序模板题了，l[rt]标记rt节点第一次进入，r[rt]表示rt节点退出，然后只要判断l[rt] + k - 1 是否小于等于r[rt]即可。 /*
Author : lifehappy
*/
#include <bits/stdc++.h>
展开全文
Description 一句话翻译(祈福12月六级考试)给一棵树,m个查询每个查询(u, k) 代表 u 节点dfs序下第k个节点 Solution 令l[i] 表示i节点的起点位置，r[i] 表示i节点的终止位置，a[i] 表示第i个数字是哪个节点。对于每个查询，查找是否在 [l[u], r[u]
展开全文
题目描述 #include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).
展开全文
不知道为什么这么裸... vec存图排个序 然后按照dfs的顺序给节点小到大编号 顺被维护一个表示节点编号是的是哪个节点... #include <bits/stdc++.h>
using namespace std;
const int maxn = 8e5+10;
struct ed
展开全文
Military Problem 题目地址： https://ac.nowcoder.com/acm/problem/112932 基本思路： 题目很长,可以概况为给你一棵树,每次查询,你要找到从开始按照遍历顺序,遍历到的第个节点,也就是找到点对应序后第个的节点就是了,然后注意超出子树的范围
展开全文
题目： 给你一棵有根树。个询问，输出从为根的子树往下得到的序列中第个数，超出则输出。 做法： 求出树的序。每个询问输出结点在中往后第个数。 代码： #include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), ci
展开全文
题意：给你一棵树，有q次查询，每次查询第n个结点的他的子树按照dfs序第x个元素是什么？ 题解：一道dfs序的裸的题目。 首先需要一个数组存放第i个结点在dfs序中的位置再需要一个数组来存放dfs序的顺序在需要一个数组来存放一个结点子树的大小。（用来判断是否需要输出-1） 每次查询首先判断他的子树大
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
