Codeforces Round#629 E. Tree Queriesweixin41923381的博客-

链接：Round #629 E

题意：

查询一棵树上的若干节点，要求找出一条满足以下条件的路径：所有查询的点在这条路径上或与该路径上的任意一点距离为1。

要思考两件事：

1.从根节点出发的路径很多，如何选择一条路径。
2.若已经选择好路径，如何判断查询的点在路径上或与路径距离为1。

如何解决：

1.对于第一点，我们考虑节点深度。从根节点出发到达每一个节点的路径都是唯一的。对于一个满足条件的路径，假设有唯一深度最大的点，这个节点要么在路径上（路径的最后一个节点），要么距离路径的距离为1（联系到深度最大这一前提，根节点到该节点也是满足条件的路径）。所以从查询点中找到深度最大的节点，即可确定路径。
2.对于第二点，我们从借助父亲节点。所有查询点的父亲节点必然在路径上。

要注意的是：

通过dfs记录每个节点的深度和父亲节点是可行的，但是若仅记录父亲节点，搜索父亲节点时会带来很大的时间资源消耗。如何能够快速的判断一个节点是否在该路径上呢？
给出这样一种解决方法：进入dfs访问某节点时，标记其访问次序，退出dfs离开某节点时，标记其退出次序。在该路径上且在终点之前的节点，其访问次序必定小于终点，其退出次序必定大于终点，这是由dfs决定的。

下面给出代码：

#include <bits/stdc++.h> 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<int> 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<re[v].size();i++){ if(re[v][i]!=fa) dfs(re[v][i],v,depth+1); }     la[v]=T,T++; } bool is_find(int u,int v){ return fi[u]<=fi[v]&&la[u]>=la[v]; } int main(){     cin.sync_with_stdio(0);     cin.tie(0);     cin >> n >> m; for(int i=0;i<n-1;i++){         cin >> 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<int> vis;         v=0; for(int i=0;i<k;i++){             cin >> u;             u--; if(dep[v]<dep[u])   v=u;//找深度最大的点             vis.push_back(u); } bool Y=true; for(int i=0;i<k;i++){             u=vis[i]; if(is_find(u,v)||is_find(par[u],v)) continue; else    Y=false; } if(Y)   cout << "YES"<<'n'; else    cout << "NO"<<'n'; } return 0; }