题目描述
难度分:1900
输入T(≤104)表示T组数据。所有数据的n之和≤105,q之和≤105。
每组数据输入n(1≤n≤105)和q(1≤q≤105)。
然后输入一棵无向树的n−1条边,节点编号从1到n。根节点是1。
然后输入一个1~n的排列p。下标从1开始。
然后输入q个询问,每个询问输入L、R(1≤L≤R≤n)、x(1≤x≤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]之中,只要这个区间里面的数出现过(利用前缀和的思想,查询有多少个数≤high,再查询有多少个数<low,两者作差就能知道有多少个数在[low,high]里面),那查询结果就是YES
,否则就是NO
。
复杂度分析
时间复杂度
跑一次dfs求出所有节点的dfn值,时间复杂度为O(n);构建主席树的时间复杂度为O(nlog2n);最后处理q个询问,每个询问要在主席树上查询,时间复杂度为O(log2n),总的时间复杂度为O(qlog2n)。因此,整个算法的时间复杂度为O((n+q)log2n)。
空间复杂度
主席树的空间复杂度为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;
}