题目描述

难度分:$1900$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$，$q$之和$\leq 10^5$。

每组数据输入$n(1 \leq n \leq 10^5)$和$q(1 \leq q \leq 10^5)$。

然后输入一棵无向树的$n-1$条边，节点编号从$1$到$n$。根节点是$1$。

然后输入一个$1$~$n$的排列$p$。下标从$1$开始。

然后输入$q$个询问，每个询问输入$L$、$R(1 \leq L \leq R \leq n)$、$x(1 \leq x \leq n)$。

对于每个询问，回答在$p[L],p[L+1],…,p[R]$这些节点中，是否存在一个节点是$x$的后代（在$x$子树中）。输出YES或NO。

输入样例

3
3 5
1 2
2 3
1 2 3
1 2 2
1 2 3
2 3 1
1 2 3
2 3 3
10 10
2 6
2 7
2 4
1 7
2 8
10 6
8 5
9 4
3 4
10 2 5 9 1 7 6 4 3 8
8 9 8
7 8 1
7 10 6
4 8 9
5 5 10
7 10 1
9 9 2
9 10 6
6 6 2
10 10 6
1 1
1
1 1 1

输出样例

YES
NO
YES
NO
YES

NO
YES
YES
YES
NO
YES
YES
NO
NO
NO

YES

算法

$DFS$序+主席树

这个题比较容易想到$dfs$序，因为求完$dfs$序，那一个子树上的问题就可以转化成一个在区间上的问题。所以构建一个数组$l$，$l[u]$表示$u$节点的$dfn$值（即$dfs$序值），因此子树$u$在$dfs$序上的范围就是$[l[u],l[u]+sz[u]-1]$，$sz[u]$是子树$u$的节点个数，这个数组也可以在$dfs$的过程中求得。

有了每个节点的$dfs$序，再将输入排列$p$中的所有元素$p[i]$，转化为$l[p[i]]$（即$p[i]=l[p[i]]$）。用$p$数组来初始化主席树，就可以利用主席树在线处理每条询问了。

对于询问$(L,R,x)$，先利用$dfs$序确定$x$子树的$dfn$值范围$[l[x],l[x]+sz[x]-1]$，令$low=l[x]$，$high=l[x]+sz[x]-1$。然后借助主席树查询$p$数组的$[L,R]$子区间上有多少个数在区间$[low,high]$之中，只要这个区间里面的数出现过（利用前缀和的思想，查询有多少个数$\leq high$，再查询有多少个数$\lt low$，两者作差就能知道有多少个数在$[low,high]$里面），那查询结果就是YES，否则就是NO。

复杂度分析

时间复杂度

跑一次$dfs$求出所有节点的$dfn$值，时间复杂度为$O(n)$；构建主席树的时间复杂度为$O(nlog_2n)$；最后处理$q$个询问，每个询问要在主席树上查询，时间复杂度为$O(log_2n)$，总的时间复杂度为$O(qlog_2n)$。因此，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

主席树的空间复杂度为$O(n)$，但是常数比较大；树的邻接表空间复杂度为$O(n)$；每个节点的$dfn$值存在$O(n)$级别的$l$数组中；以每个节点为根的子树大小存在$O(n)$级别的$sz$数组中。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int n, q, T, ts, l[N], sz[N];
vector<int> graph[N];

void dfs(int u, int fa) {
    l[u] = ++ts;
    sz[u] = 1;
    for(int v: graph[u]) {
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

class ChairTree {
public:
    int tot, n, m;
    vector<int> root, a, lchild, rchild, cnt;
    // 用数组nums初始化主席树
    explicit ChairTree(vector<int>& nums, int EXP=20) {
        n = nums.size();      // 原始元素个数
        root.resize(n + 1);
        a.resize(n + 1);
        lchild.resize(n * EXP);
        rchild.resize(n * EXP);
        cnt.resize(n * EXP);
        for(int i = 1; i <= n; i++) {
            a[i] = nums[i - 1];
        }
        sort(a.begin() + 1, a.end());
        m = unique(a.begin() + 1, a.end()) - a.begin() - 1;      // 去重元素个数
        tot = 0;
        root[0] = build(1, m);
        for(int i = 1; i <= n; i++){
            int temp = lower_bound(a.begin() + 1, a.begin() + m + 1, nums[i - 1]) - a.begin();
            root[i] = update(root[i - 1], 1, m, temp);
        }
    }

    int build(int l, int r) {
        int id = ++tot;
        if(l < r) {
            int mid = l + r >> 1;
            lchild[id] = build(l, mid);
            rchild[id] = build(mid + 1, r);
        }
        return id;
    }

    // 子数组[l,r]中第k小的值，k从1开始取
    int kth(int l, int r, int k) {
        ++l, ++r;
        return kth(root[l - 1], root[r], 1, m, k);
    }

    // 子数组[l,r]中小于等于k的元素数量
    int leqcnt(int l, int r, int k) {
        ++l, ++r;
        int temp = upper_bound(a.begin() + 1, a.begin() + 1 + m, k) - a.begin() - 1;
        if(temp == 0) return 0;
        return leqcnt(root[l - 1], root[r], 1, m, temp);
    }

private:
    int update(int pre, int l, int r, int x) {
        int id = ++tot;
        lchild[id] = lchild[pre];
        rchild[id] = rchild[pre];
        cnt[id] = cnt[pre] + 1;
        if(l < r) {
            int mid = l + r >> 1;
            if(x <= mid) {
                lchild[id] = update(lchild[pre], l, mid, x);
            }else {
                rchild[id] = update(rchild[pre], mid + 1, r, x);
            }
        }
        return id;
    }

    int kth(int u, int v, int l, int r, int k) {
        if(l >= r) return l;
        int x = cnt[lchild[v]] - cnt[lchild[u]];
        int mid = l + r >> 1;
        if(x >= k) {
            return kth(lchild[u], lchild[v], l, mid, k);
        }else {
            return kth(rchild[u], rchild[v], mid + 1, r, k - x);
        }
    }

    int leqcnt(int u, int v, int l, int r, int k) {
        int mid = l + r >> 1;
        int ans = 0;
        if(l == r) {
            return cnt[v] - cnt[u];
        }
        if(k <= mid) {
            ans += leqcnt(lchild[u], lchild[v], l, mid, k);
        }else {
            ans += cnt[lchild[v]] - cnt[lchild[u]];
            ans += leqcnt(rchild[u], rchild[v], mid + 1, r, k);
        }
        return ans;
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) {
            graph[i].clear();
        }
        for(int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        // 求DFS序
        ts = 0;
        dfs(1, 0);
        vector<int> p;
        for(int i = 0; i < n; i++) {
            int id;
            scanf("%d", &id);
            p.push_back(l[id]);
        }
        ChairTree tree(p);
        for(int i = 1; i <= q; i++) {
            int L, R, x;
            scanf("%d%d%d", &L, &R, &x);
            int low = l[x], high = l[x] + sz[x] - 1;    // x子树的范围
            // 检查[L,R]中有没有在[low,high]里面的数
            puts(tree.leqcnt(L - 1, R - 1, high) > tree.leqcnt(L - 1, R - 1, low - 1)? "YES": "NO");
        }
        puts("");
    }
    return 0;
}