Codeforces|Codeforces Round#629 E. Tree Queries
【Codeforces|Codeforces Round#629 E. Tree Queries】链接：Round #629 E
- 题意：
- 查询一棵树上的若干节点，要求找出一条满足以下条件的路径：所有查询的点在这条路径上或与该路径上的任意一点距离为1。
- 要思考两件事：
-
1.从根节点出发的路径很多，如何选择一条路径。
2.若已经选择好路径，如何判断查询的点在路径上或与路径距离为1。 - 如何解决：
-
1.对于第一点，我们考虑
节点深度。从根节点出发到达每一个节点的路径都是唯一的。对于一个满足条件的路径，假设有唯一深度最大的点，这个节点要么在路径上（路径的最后一个节点），要么距离路径的距离为1（联系到深度最大这一前提，根节点到该节点也是满足条件的路径）。所以从查询点中找到深度最大的节点，即可确定路径。
2.对于第二点，我们从借助 父亲节点。所有查询点的父亲节点必然在路径上。 - 要注意的是：
-
通过dfs记录每个节点的深度和父亲节点是可行的，但是若仅记录父亲节点，搜索父亲节点时会带来很大的时间资源消耗。如何能够
快速的判断一个节点是否在该路径上呢？
给出这样一种解决方法：进入dfs访问某节点时，标记其 访问次序，退出dfs离开某节点时，标记其 退出次序。在该路径上且在终点之前的节点，其访问次序必定小于终点，其退出次序必定大于终点，这是由dfs决定的。
#include
using namespace std;
/*
如何确定一条路径——找到深度最大的点
如何判断点是否在路径上——通过记录的出现情况
*/const int MAX_N = 2e5+10;
const int MAX_M = 2e5+10;
const int MAX_K = 2e5+10;
int par[MAX_N];
int dep[MAX_N];
int fi[MAX_N];
int la[MAX_N];
vector re[MAX_N];
int n,m;
int u,v,k;
int T;
void dfs(int v,int fa,int depth){
dep[v]=depth;
par[v]=fa;
//确定每个点的parent和depth
fi[v]=T,T++;
for(int i=0;
i=la[v];
}int main(){
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0;
i> u >> v;
u--,v--;
re[u].push_back(v);
re[v].push_back(u);
}
T=0;
dfs(0,-1,0);
while(m--){
cin >> k;
vector vis;
v=0;
for(int i=0;
i> u;
u--;
if(dep[v] 推荐阅读
- 怀念三里屯那家叫做the|怀念三里屯那家叫做the tree 的酒吧
- ztree|ztree 拖拽
- SourceTree|SourceTree 教程文档（了解界面）
- cs61b week8 -- Binary Search Tree
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars
- codeforces C. Omkar and Waterslide
- codeforces B. Omkar and Infinity Clock
- codeforces B. Ternary Sequence