E. Tree Queries（思维 + lca / 欧拉序列）

题目链接

分析一下：
思维思维，还是思维...

1. 思维转换 + lca
首先考虑选一个点u作为标准，如果说这个点选的比较浅，那么我们比较深的点就难以满足；
因此我们要选深度最深的点作为标准。（不会证明...也没找到...）

然后以根节点 到 这个点u的路径作为标准，我们可以发现，如果满足条件的话；
则其他点到这条路径上的距离<=1，也就是u和每个点的lca都在这条路径上：

<=> dep[v] - dep[lca(u,v)] <= 1（其实这个感觉也挺难想的...）
或者<=> fv为v的父节点，然后lca(fv,u) = fv（即v的父节点一定再路径上）

2. dfs(欧拉序列判断)(思维)
由上面的第二个等价我们可以想到，只需要判断其他点是否在标准路径上就行;
怎么判断呢？？？欧拉序列！！！

之前写过欧拉序列，从根节点dfs，每个点记录第一次出现和最后一次出现；
如果在a b一条路径上的话(假设a浅b深)，则b在序列中的两个下标一定被包含在a的两个下标中：
即a.first ... b.first ... b.second ... a.second

所以我们可以dfs，然后记录每个点的下标，判断其他点(已经变为其父节点)的下标是否包含最深点的下标就行

虽然说代码还是很长

lca的

int h[maxn],ne[maxn*2],e[maxn*2],idx;
int depth[maxn],f[maxn][20];    //2^15 > 4e4，所以15就可以跳完所有边
int n,m;
int p[maxn];

int add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}

void bfs(int root)  //预处理depth[] 和 f[][]数组, 从根开始向下更新 
{
    memset(depth,0x3f,sizeof depth);
    depth[0] = 0;       //设置哨兵，处理跳出根节点了 
    depth[root] = 1;

    queue<int> q;
    q.push(root);

    while(q.size())
    {
        int no = q.front(); //父节点 
        q.pop();

        for(int i=h[no]; i!=-1; i=ne[i])    //子节点 
        {
            int j = e[i];

            //更新两个数组
            if(depth[j] > depth[no] + 1)    //还没更新过
            {
                depth[j] = depth[no] + 1;

                q.push(j);

                f[j][0] = no;   //子节点跳一步到父节点
                for(int k=1; k<=19; k++)    //枚举往上跳2^k步 
                    f[j][k] = f[f[j][k-1]][k-1];    //2^k = 2^(k-1) + 2^(k-1)               
            }
        }   
    }
}

int lca(int a,int b)
{
    //第一步，两个点先跳到同一层
    if(depth[a] < depth[b]) swap(a,b);  //让a跳到b那一层
    for(int k=19; k>=0; k--)    //从大到小枚举跳的步数
        if(depth[f[a][k]] >= depth[b])  //如果a跳完之后不超过b，则可以跳 
            a = f[a][k];

    if(a == b) return b;    //跳到同一层后相等说明b就是公共祖先了

    //否则，a b同时往上跳 
    for(int k=19; k>=0; k--)
        if(f[a][k] != f[b][k])  //跳完之后不相等一直跳 
        {
            a = f[a][k];
            b = f[b][k];    //跳到最近公共祖先的下一层为止 
        }

    return f[a][0]; //在往上跳一步就是最近公共祖先了 
}

int main()
{
    memset(h,-1,sizeof h);

    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;

        add(a,b);
        add(b,a);
    }

    bfs(1);

    while(m--)
    {
        int k;
        cin>>k;

        int maxi = 0;
        int id;
        for(int i=1;i<=k;i++)
        {
            cin>>p[i];

            if(depth[p[i]] > maxi)
            {
                maxi = depth[p[i]];
                id = p[i];
            }
        }

        int flag = 1;
        for(int i=1;i<=k;i++)
        {
            if(p[i] == id) continue;

            int fab = lca(id,p[i]);

            if(depth[p[i]] - depth[fab] > 1)
            {
                flag = 0;
                break;
            }
        }

        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }


    return 0;
}

欧拉序列 的

int h[maxn],ne[maxn*2],e[maxn*2],idx;
int dep[maxn];
int f[maxn];    //每个点的父节点
int n,m;

PII pos[maxn];  //每个点两次出现的下标
int cnt;

int v[maxn];

void add(int a,int b)
{
    e[idx]=b; ne[idx]=h[a]; h[a]=idx++;
}

void bfs(int root)
{
    queue<int> q;
    q.push(root);

    dep[root] = 0;
    f[root] = root;

    while(q.size())
    {
        int u = q.front();
        q.pop();

        for(int i=h[u];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dep[j] != -1) continue;

            dep[j] = dep[u] + 1;
            f[j] = u;

            q.push(j);
        }
    }
}

void dfs(int u,int fa)
{
    pos[u].first = ++cnt;

    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i];

        if(j == fa) continue;

        dfs(j,u);
    }

    pos[u].second = ++cnt;
}

int main()
{
    memset(h,-1,sizeof h);
    memset(dep,-1,sizeof dep);

    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    bfs(1); //求一下深度 和 父节点

    dfs(1,-1);

    while(m--)
    {
        int k;
        cin>>k;

        int maxi = -1;
        int id;
        for(int i=1;i<=k;i++)
        {
            cin>>v[i];

            if(dep[v[i]] > maxi)
            {
                maxi = dep[v[i]];
                id = v[i];
            }
        }

        int flag = 1;
        for(int i=1;i<=k;i++)
        {
            if(v[i] == id) continue;

            int fv = f[v[i]];   //变成父节点

            //不合法
            if(!(pos[fv].first <= pos[id].first && pos[fv].second >= pos[id].second))
            {
                flag = 0;
                break;
            }
        }

        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }

    return 0;
}