CF1328E Tree Queries

题意

给定一棵以 \(1\) 为根节点的有根树。

现在有 \(q\) 次询问，每次询问给定 \(m\) 个节点，问是否存在一条从根节点开始的链，使得每个节点到这条链的距离不超过 \(1\) 。

思路

我们首先可以给出一个结论：如果节点 \(v\) 与一条链的距离不超过 \(1\) ，那么其父亲节点一定位于这条链上。我们可以很简单的证明这个结论。

当点 \(v\) 正好在这条链上时，那么其父亲节点正好位于根节点与 \(v\) 的路径上，也就是位于链上；
当点 \(v\) 与链的距离为 \(1\) 时，由于该链的起点为根节点，那么意味着这条链经过 \(v\) 的父亲节点，但是没有到达 \(v\) ，否则由于树上路径唯一，链不可能经过 \(v\) 的儿子节点。

综上，我们可以将问题转化为：给定的节点的父亲节点是否在一条以根节点为起点的树链上。

对于这个问题，我们可以先对所有给定节点的父亲节点按照深度排序。因为对于任意一个节点，其一定与根节点是在一条链上的，因此我们要验证的是，所有节点之间是否在一条链上。

我们考虑为什么任意一个节点一定与根节点是在同一条链上的问题。对于任意一个节点，其一定是在根节点的子树之内，树上两点之间有且仅有一条简单路径，因此该子问题得到验证。

那么我们想要知道这 \(m\) 个父亲节点是否是在同一条链上。还记得我们按照深度排序了吗？如果这几个节点在同一条链上，意味着深度更深的节点一定位于深度浅的节点的子树内，若不在子树内，则意味着根节点不再作为链的端点，而是链的中间一部分，这条链需要绕过根节点。

综上所述，我们可以先对整棵树计算一次深度、 dfs 序、子树节点个数后，对于每次询问，我们将节点转化为其父亲节点，并按照深度从小到大排序，最后验证深度大的节点是否位于前一个深度小的子树，即可。

实现

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    std::cin >> n >> q;

    std::vector adj(n, std::vector<int>{});
    for (int i = 0; i < n - 1; i ++) {
        int u, v;
        std::cin >> u >> v;
        u --; v --;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    std::vector<int> dep(n, -1), dfn(dep), siz(dep), fa(dep);
    auto dfs = [&, stamp{-1}](auto &self, int from, int come) mutable -> void {
        dfn[from] = ++ stamp;
        siz[from] = 1;
        fa[from] = come;
        for (auto to : adj[from]) {
            if (dep[to] == -1) {
                dep[to] = dep[from] + 1;
                self(self, to, from);
                siz[from] += siz[to];
            }
        }
    };
    dep[0] = 0;
    dfs(dfs, 0, 0);
    
    for (int t = 0; t < q; t ++) {
        int m;
        std::cin >> m;
        std::vector<int> ls(m);
        for (auto &item : ls) {
            std::cin >> item;
            item --;
            item = fa[item];
        }
        std::ranges::sort(ls, std::less{}, [&](auto x) { return dep[x]; });

        bool ok = true;
        for (int i = 1; i < m && ok; i ++) {
            int pre = ls[i - 1], now = ls[i];
            ok &= (dfn[pre] <= dfn[now] && dfn[now] <= dfn[pre] + siz[pre] - 1);
        };

        if (ok) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}