嘘~ 正在从服务器偷取页面 . . .

CF1328E Tree Queries 题解

发布日期: 2022-11-01

更新日期: 2022-11-01

文章字数: 503

CF1328E Tree Queries 题解

题意：

给你一个以 $1$ 为根的有根树.

每回询问 $k$ 个节点 ${v_1, v_2 \cdots ,v_k}$

求出是否有一条以根节点为一端的链使得询问的每个节点到此链的距离均 $\leq 1$.

只需输出可行性, 无需输出方案。

懒得修题面，输出 YES 或 NO 就好了。

$2\le n \le 2\times 10^5,1\le ~\sum k \le 2\times 10^5$ 。

钦定 $1$ 为根，并钦定 $1$ 的父亲也为 $1$ ，则合法的点的父亲均在一条链上。

判断一个结点 $y$ 是否在 $x$ 的子树内：

$\mathtt{dfn[x] \le dfn[y] \land dfn[y] < dfn[x] + sz[x]}$

时间复杂度 $\mathcal{O}(n + \sum k \log \sum k)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))

int n,Q,pos=1,dep[N],fa[N],sz[N],dfn[N],tmp[N],head[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int f)
{
    static int tim = 0;
    dfn[u] = ++tim; dep[u] = dep[f] + 1; fa[u] = f; sz[u] = 1;
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v != f) { dfs(e[i].v, u); sz[u] += sz[e[i].v]; }
}
bool in(int x,int y) // y in x's subtree ? 
{ return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + sz[x]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i=1,u,v; i<n; i++) { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    for(dfs(1,1); Q--; )
    {
        int k,x; cin >> k;
        for(int i=1,x; i<=k; i++) { cin >> x; tmp[i] = fa[x]; }
        sort(tmp + 1, tmp + 1 + k, [](int x,int y) { return dep[x] < dep[y]; });
        bool ok = 1;
        for(int i=1; i<k; i++) if(!in(tmp[i], tmp[i+1])) ok = 0;
        cout << (ok ? "YES\n" : "NO\n");
    }
    return 0;
}