Codeforces Round #629 (Div. 3) E. Tree Queries LCA

缺乏、安全感 2023-05-28 05:15 1阅读 0赞

题目链接：https://codeforces.com/contest/1328/problem/E  
题意：给你一棵树，多次询问每次给你一个集合，问你能否选一条链使得集合所有点到这条链的距离不大于1  
思路：每次将集合按照深度排序，然后我们用深度最大的点和其余点依次求LCA，然后判断深度差是否大于1  
如果大于就说明不满足。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 2e5 + 10;
    const int inf = 0x3f3f3f3f;
    //head[u] 和 tot的初始值都为-1
    int head[maxn << 1], nxt[maxn << 1], to[maxn << 1], ver[maxn << 1];
    int f[maxn][22], d[maxn], dis[maxn], a[maxn]; //d[x]表示x的深度, dis[y]表示y到根的距离
    int n, m, s, lg, tot = -1;
    queue<int> q;
    void add(int u, int v, int w)
    {
    	nxt[++tot] = head[u]; //当前边的后继
    	head[u] = tot; //起点u的第一条边
    	to[tot] = v; //当前边的终点
    	ver[tot] = w; //当前边的权值
    }
    void bfs(int s)
    {
        while(!q.empty()) q.pop();
        q.push(s), d[s] = 1;
        while(!q.empty())
        {
            int u = q.front(); q.pop();
            for(int i = head[u]; ~i; i = nxt[i])
            {
                int v = to[i];
                if(d[v]) continue;
                d[v] = d[u] + 1;
                dis[v] = dis[u] + ver[i];
                f[v][0] = u;
                for(int j = 1; j <= lg; ++j)
                    f[v][j] = f[f[v][j - 1]][j - 1];
                q.push(v);
            }
        }
    }
    int LCA(int u, int v)
    {
        if(d[u] > d[v]) swap(u, v);
        for(int i = lg; i >= 0; --i) //u是v的祖先的情况
        {
            if(d[f[v][i]] >= d[u]) //不在同一条链上就处理到深度相同
                v = f[v][i];
        }
        if(u == v) return u;
        for(int i = lg; i >= 0; --i) //深度相同就可以同时倍增求
        {
            if(f[u][i] != f[v][i])
                u = f[u][i], v = f[v][i];
        }
        return f[u][0];
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        lg = (int)(log(n) / log(2)) + 1; //枚举的深度
        for(int i = 0; i <= n; ++i) head[i] = -1, d[i] = 0;
        tot = -1;
        for(int i = 1; i < n; ++i)
        {
            int u, v, w = 1;
            scanf("%d%d", &u, &v);
            add(u, v, w), add(v, u, w);
        }
        bfs(1); //s是根节点
        while(m--)
        {
            int k, Max = 0, id;
            scanf("%d", &k);
            for(int i = 1; i <= k; ++i)
            {
                scanf("%d", &a[i]);
                if(Max < d[a[i]])
                    Max = d[a[i]], id = a[i];
            }
            int flag = 1;
            for(int i = 1; i <= k; ++i)
            {
                int fa = LCA(id, a[i]);
                if(abs(d[fa] - d[a[i]]) > 1)
                {
                    flag = 0;
                    break;
                }
            }
            if(flag) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }