Codeforces Round #629 (Div. 3)E 能否找到含指定k个节点的路径

题意：给定一棵树，q个询问，每个询问k个节点，问能否找出一条从根节点到任意点的简单路径，使这k个点要么在路径上要么距离这条路径距离为1

分析：对于每个节点转换为他的fa ，那么问题就变成了能否找到一条路径包含这些fa。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int M=2e5+4;
const int inf=0x3f3f3f3f;
vector<int>g[M];
int dfn[M],ed[M],tot,f[M];
void dfs(int u,int fa){
    dfn[u]=++tot;
    f[u]=fa;
    for(auto v:g[u]){
        if(v!=fa)
            dfs(v,u);
    }
    ed[u]=tot;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,0);
 
    while(m--){
        int k;
        scanf("%d",&k);
        int minn=inf,maxx=0;
        while(k--){
            int x;
            scanf("%d",&x);
            if(x!=1)
                x=f[x];
            minn=min(minn,ed[x]);
            maxx=max(maxx,dfn[x]);
 
        }
        if(minn>=maxx)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

View Code