CF-1328 E. Tree Queries

E. Tree Queries

题目链接

题意

给定一个树，每次询问一组点，问是否存在一条从根到某点的路径，使得该组点到该路径的最短距离不超过1

分析

从根到达某点的路径，如果覆盖到了某个点，那么一定会覆盖它的父亲（根除外），所以对组内的点替换成他们的父亲，问题转换为是否存在一条从根出发的路径覆盖所有的点。做法是将这些点按照深度从小到大排序，然后深度小的必须为深度大的的祖先

相邻两点求LCA即可，由于题目特殊性，前面的点和后面的点必须和根在一条直直的路径上，所以可以用欧拉序直接来判断是否可行

另外求LCA的方法主要有四种，倍增，Tarjan离线，树剖，还有一种就是欧拉序上面RMQ

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 200000 + 5;

int head[N], ver[N<<1], nxt[N<<1], tot;

int f[N][20], dep[N], a[N];

int n, m;

void add(int x, int y){

    ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;

}

void dfs(int x, int fa){

    for(int i=head[x];i;i=nxt[i]){

        int y = ver[i];

        if(y == fa) continue;

        dep[y] = dep[x] + 1;

        f[y][0] = x;

        dfs(y, x);

    }

}

int lca(int x, int y){

    if(dep[x] > dep[y]) swap(x, y);

    for(int i=19;i>=0;i--) if(dep[f[y][i]] >= dep[x]) y = f[y][i];

    if(x == y) return x;

    for(int i=19;i>=0;i--) if(f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];

    return f[x][0];

}

int main(){

    scanf("%d%d", &n, &m);

    for(int i=2;i<=n;i++){

        int x, y;

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

    dep[1] = 1;

    dfs(1, 0);

    for(int j=1;j<=19;j++){

        for(int i=1;i<=n;i++){

            f[i][j] = f[f[i][j-1]][j-1];

        }

    }

    while(m--){

        int k;scanf("%d", &k);

        for(int i=1;i<=k;i++){

            scanf("%d", &a[i]);

            a[i] = f[a[i]][0];

        }

        sort(a + 1, a + 1 + k, [](int x, int y)->bool{ return dep[x] < dep[y]; });

        bool flag = true;

        for(int i=2;i<=k;i++){

            if(lca(a[i-1], a[i]) != a[i-1]){

                flag = false;

                break;

            }

        }

        puts(flag ? "YES":"NO");

    }

    return 0;

}

CF-1328 E. Tree Queries的相关教程结束。