Codeforces Round#629 E. Tree Queries

Elaine ·

更新时间:2024-09-20

· 837 次阅读

链接：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<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]=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]<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;
}

作者：夏弥耶

CodeForces round tree

1024 个赞