给定有n个结点的树和长度为n的排列，q次询问：l, r, x, 若p[l, r]中存在至少一个结点是x的后代，输出yes，否则输出no

本文主要是介绍给定有n个结点的树和长度为n的排列，q次询问：l, r, x, 若p[l, r]中存在至少一个结点是x的后代，输出yes，否则输出no，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int n, q;
vector<int> G[maxn];
int L[maxn], R[maxn];//L[i]表示结点i的时间戳，R[i]表示结点i的后代中时间戳的最大值
int p[maxn];
int t[maxn];
struct Node{int id, flag, x;//id：第几次询问，flag：0为左端点，1为右端点，x：询问结点
};
vector<Node> Q[maxn];//Q[i]存询问区间左端点-1为i或右端点为i的询问
int tot;
int ans[maxn][2];//ans[i][0]:第i次询问，设询问区间为[l, r], 询问结点为x，只考虑p[1, l - 1], 有多少个结点的时间戳在[L[x], R[x]]范围内， ans[i][1]:考虑p[1, r],有多少个结点时间戳在[L[x], R[x]]内
void dfs(int u, int fa){L[u] = ++tot;for(auto v : G[u]){if(v == fa) continue;dfs(v, u);}R[u] = tot;
}
int lowbit(int x){return x & (-x);
}
void add(int x, int k){for(int i = x; i <= n; i += lowbit(i)){t[i] += k;}
}
int ask(int x){int res = 0;for(int i = x; i >= 1; i -= lowbit(i)){res += t[i];}return res;
}
void init(){for(int i = 1; i <= n; i++){G[i].clear();t[i] = 0;}tot = 0;for(int i = 1; i <= q; i++){Q[i].clear();ans[i][0] = ans[i][1] = 0;}
}
void solve(){//int n, q;cin >> n >> q;init();for(int i = 1; i < n; i++){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}for(int i = 1; i <= n; i++){cin >> p[i];}for(int i = 1; i <= q; i++){int l, r, x;cin >> l >> r >> x;l--;//！！！！Q[l].push_back({i, 0, x});Q[r].push_back({i, 1, x});}dfs(1, 0);for(int i = 1; i <= n; i++){// for(auto [id, flag, x] : Q[i]){// 	if(flag == 1) continue;// 	ans[id][flag] = ask(R[x]) - ask(L[x] - 1);// }int u = p[i];int pos = L[u];add(pos, 1);for(auto [id, flag, x] : Q[i]){//if(flag == 0) continue;ans[id][flag] = ask(R[x]) - ask(L[x] - 1);}}for(int i = 1; i <= q; i++){if(ans[i][0] == ans[i][1]) cout << "No\n";else cout << "Yes\n";}cout << '\n';
}
int main(){ios::sync_with_stdio(0);cin.tie(0);int T;cin >> T;while(T--){solve();}// map<int, int> mp;// mp[1] = 1;// mp[2] = 2;// for(auto [x, y] : mp){// 	cout << x << ' ' << y;// }return 0;
}

这篇关于给定有n个结点的树和长度为n的排列，q次询问：l, r, x, 若p[l, r]中存在至少一个结点是x的后代，输出yes，否则输出no的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---