Codeforces 1328E Tree Queries

题意：

给出一颗树，以1为根节点。

每次询问给出一组节点，询问是否存在从根节点开始的链使得所有节点本身或父亲在链上

题解：

猜想这条链的终点一定是最深的那个节点。

考虑用倍增LCA做。

遍历询问序列，比较当前节点和最深节点的LCA与当前节点的高度差，如果大于1直接输出NO。

时间复杂度是O(NMlogN)，用链式前向星存图会T，一定要用vector存，不知道为什么...

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int N,M;
vector<int> g[maxn];
int father[20][maxn];
int h[maxn];
void dfs (int x) {
    for (int i=0;i<g[x].size();i++) {
        int v=g[x][i];
        if (v==father[0][x]) continue;
        father[0][v]=x;
        h[v]=h[x]+1;
        dfs(v);
    }
}
int lca (int x,int y) {
    if (h[x]<h[y]) swap(x,y);
    for (int i=17;i>=0;i--)
        if (h[x]-h[y]>>i) x=father[i][x];
    if (x==y) return x;
    for (int i=17;i>=0;i--) 
        if (father[i][x]!=father[i][y]) {
            x=father[i][x];
            y=father[i][y];
        }
    return father[0][x];
}
int q[maxn];
int main () {
    scanf("%d%d",&N,&M);
    for (int i=0;i<N-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);
    for (int i=1;i<=17;i++)
        for (int j=1;j<=N;j++)
            father[i][j]=father[i-1][father[i-1][j]];
    for (int i=0;i<M;i++) {
        int k;
        scanf("%d",&k);
        int Max=-1,u=-1;
        for (int j=1;j<=k;j++) {
            scanf("%d",&q[j]);
            if (h[q[j]]>Max) Max=h[q[j]],u=j;
        }
        int flag=1;
        for (int j=1;j<=k;j++) {
            int lc=lca(q[j],q[u]);
            if (abs(h[lc]-h[q[j]])>1) {
                flag=0;
                break;
            }
        }
        if (flag) 
            printf("YES
");
        else 
            printf("NO
");
    }
    return 0;
}