Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define _test int _TEST; cin>>_TEST; while(_TEST--)
- #define pb push_back
- class SegTree
- {
- public:
- const int N = 1000005;
- int n;
- int *_X;
- int res ;
- SegTree()
- {_X = new int[N];}
- void init(vector<int> &arr, int n)
- {this->n = n;_Y(arr);}
- void _Y(vector<int> &arr)
- {
- for (int i = 0; i < n; ++i)_X[n+i]=arr[i];
- for (int i = n - 1; i > 0; --i)_X[i] = min(_X[i<<1] , _X[i<<1|1]);
- }
- void _Z(int l, int r)
- {
- for (l += n, r += n; l < r; l >>= 1, r >>= 1)
- {if (l&1)res = min(res, _X[l++]);
- if (r&1)res = min(res, _X[--r]);}
- }
- ll int _G(int l, int r)
- {res = 1e9;_Z(l, r);return res;}
- void _H(int p, int value)
- {for (_X[p += n] = value; p > 1; p >>= 1)_X[p>>1] = min(_X[p] , _X[p^1]);}
- };
- int main()
- {
- SegTree sgt;
- _test
- {
- int n, q;
- cin>>n>>q;
- vector<vector<int>> tree(n);
- for(int i=0; i<n-1; i++)
- {
- int u, v;
- cin>>u>>v;
- u--, v--;
- tree[u].pb(v);
- tree[v].pb(u);
- }
- vector<int> p(n);
- for(auto &e: p) cin>>e;
- vector<int> st(n), en(n), ord;
- int t = 0;
- function<void(int, int)> DFS = [&](int u, int p)
- {
- st[u] = en[u] = t++;
- ord.pb(u);
- for(auto v: tree[u])
- {
- if(p == v) continue;
- DFS(v, u);
- en[u] = max(en[u], en[v]);
- }
- };
- DFS(0, -1);
- vector<vector<array<int, 3>>> queries(n);
- for(int i=0; i<q; i++)
- {
- int l, r, x;
- cin>>l>>r>>x;
- l--, r--, x--;
- queries[x].pb({l, r, i});
- }
- vector<int> ans(q);
- vector<int> vals(n);
- vector<int> pos(n);
- for(int i=0; i<n; i++)
- {
- p[i]--;
- pos[p[i]] = i;
- vals[i] = st[p[i]];
- }
- sgt.init(vals, n);
- for(int i=0; i<n; i++)
- {
- int u = ord[i], tmp;
- for(auto [l, r, ind]: queries[u])
- {
- tmp = sgt._G(l, r+1);
- ans[ind] = (tmp <= en[u]);
- }
- sgt._H(pos[u], 1e9);
- }
- for(auto e: ans)
- {
- if(e) cout<<"YES\n";
- else cout<<"NO\n";
- }
- cout<<"\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment