Ankit_132

G

Nov 17th, 2023
563
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.60 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. #define ll     long long
  8. #define _test   int _TEST; cin>>_TEST; while(_TEST--)
  9. #define pb     push_back
  10.  
  11. class SegTree
  12. {
  13.     public:
  14.     const int N = 1000005;
  15.  
  16.     int n;
  17.     int  *_X;
  18.     int res ;
  19.  
  20.     SegTree()
  21.     {_X = new int[N];}
  22.  
  23.     void init(vector<int> &arr, int n)
  24.     {this->n = n;_Y(arr);}
  25.  
  26.     void _Y(vector<int> &arr)
  27.     {
  28.         for (int i = 0; i < n; ++i)_X[n+i]=arr[i];
  29.         for (int i = n - 1; i > 0; --i)_X[i] = min(_X[i<<1] , _X[i<<1|1]);
  30.     }
  31.  
  32.     void _Z(int l, int r)
  33.     {
  34.         for (l += n, r += n; l < r; l >>= 1, r >>= 1)
  35.         {if (l&1)res = min(res, _X[l++]);
  36.             if (r&1)res = min(res, _X[--r]);}
  37.     }
  38.  
  39.     ll int _G(int l, int r)
  40.     {res = 1e9;_Z(l, r);return res;}
  41.  
  42.     void _H(int p, int value)
  43.     {for (_X[p += n] = value; p > 1; p >>= 1)_X[p>>1] = min(_X[p] , _X[p^1]);}
  44. };
  45.  
  46. int main()
  47. {
  48.     SegTree sgt;
  49.  
  50.     _test
  51.     {
  52.         int n, q;
  53.         cin>>n>>q;
  54.  
  55.         vector<vector<int>> tree(n);
  56.  
  57.         for(int i=0; i<n-1; i++)
  58.         {
  59.             int u, v;
  60.             cin>>u>>v;
  61.  
  62.             u--, v--;
  63.  
  64.             tree[u].pb(v);
  65.             tree[v].pb(u);
  66.         }
  67.  
  68.         vector<int> p(n);
  69.         for(auto &e: p)     cin>>e;
  70.  
  71.         vector<int> st(n), en(n), ord;
  72.         int t = 0;
  73.  
  74.         function<void(int, int)> DFS = [&](int u, int p)
  75.         {
  76.             st[u] = en[u] = t++;
  77.             ord.pb(u);
  78.  
  79.             for(auto v: tree[u])
  80.             {
  81.                 if(p == v)      continue;
  82.  
  83.                 DFS(v, u);
  84.                 en[u] = max(en[u], en[v]);
  85.             }
  86.         };
  87.  
  88.         DFS(0, -1);
  89.  
  90.         vector<vector<array<int, 3>>> queries(n);
  91.  
  92.         for(int i=0; i<q; i++)
  93.         {
  94.             int l, r, x;
  95.             cin>>l>>r>>x;
  96.  
  97.             l--, r--, x--;
  98.  
  99.             queries[x].pb({l, r, i});
  100.         }
  101.  
  102.         vector<int> ans(q);
  103.  
  104.         vector<int> vals(n);
  105.         vector<int> pos(n);
  106.  
  107.         for(int i=0; i<n; i++)
  108.         {
  109.             p[i]--;
  110.             pos[p[i]] = i;
  111.             vals[i] = st[p[i]];
  112.         }
  113.  
  114.         sgt.init(vals, n);
  115.  
  116.         for(int i=0; i<n; i++)
  117.         {
  118.             int u = ord[i], tmp;
  119.  
  120.             for(auto [l, r, ind]: queries[u])
  121.             {
  122.                 tmp = sgt._G(l, r+1);
  123.  
  124.                 ans[ind] = (tmp <= en[u]);
  125.             }
  126.  
  127.             sgt._H(pos[u], 1e9);
  128.         }
  129.  
  130.         for(auto e: ans)
  131.         {
  132.             if(e)       cout<<"YES\n";
  133.             else        cout<<"NO\n";
  134.         }
  135.         cout<<"\n";
  136.     }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment