fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#pragma GCC optimize "trapv"
  3. //#include<ext/pb_ds/assoc_container.hpp>
  4. //#include<ext/pb_ds/tree_policy.hpp>
  5. #define fast_az_fuk      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  6. #define ll               long long
  7. #define lll              __int128
  8. #define ull              unsigned ll
  9. #define ld               long double 
  10. #define pb               push_back 
  11. #define pf               push_front
  12. #define dll              deque<ll> 
  13. #define vll              vector<ll>
  14. #define vvll             vector<vll> 
  15. #define pll              pair<ll,ll> 
  16. #define vpll             vector<pll>
  17. #define dpll             deque<pll>
  18. #define mapll            map<ll,ll>
  19. #define umapll           umap<ll,ll>
  20. #define endl             "\n" 
  21. #define all(v)           v.begin(),v.end() 
  22. #define ms(a,x)          memset(a,x,sizeof(a))
  23. #define random(l,r,T)    uniform_int_distribution<T>(l,r)(rng)
  24.  
  25.  
  26. //#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  27.  
  28. using namespace std;
  29.  
  30.  
  31. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. //using namespace __gnu_pbds;
  33.  
  34. template<typename T> istream& operator >>(istream &in,vector<T> &v){ for(auto &x:v) in>>x; return in;}
  35. template<typename T> ostream& operator <<(ostream &out,const vector<T> &v){ for(auto &x:v) out<<x<<' '; return out;}
  36. template<typename T1,typename T2> istream& operator >>(istream &in,pair<T1,T2> &p){ in>>p.first>>p.second; return in;}
  37. template<typename T1,typename T2> ostream& operator <<(ostream &out,const pair<T1,T2> &p){ out<<p.first<<' '<<p.second; return out;}
  38. vvll adj,ind; vll level; ll cnt;
  39. void dfs(ll node=1,ll par=1,ll lev=0){
  40.     level[node] = lev;
  41.     ind[node].pb(cnt++); 
  42.     for(ll x:adj[node]){
  43.         if(x==par) continue;
  44.         dfs(x,node,lev+1);
  45.         ind[node].pb(cnt++);
  46.     }
  47. }
  48. class seg_tree{
  49. private:
  50.     const ll reset = 0;
  51.     int n; bool indx; vll st;
  52.     void createTree(int,int,int,const vll&); 
  53.     void update(int,int,int,const ll&,const int&,const int&); 
  54.     ll query(int,int,int,const int&,const int&); 
  55.     ll merge_operation(ll i,ll j){
  56.         if(level[i] < level[j]) return i;
  57.         else if(level[j] < level[i]) return j;
  58.         else return min(i,j);
  59.     }
  60.     // Lazy Propagation
  61.     vll lazy; void lazyPush(int,int,int);
  62. public:
  63.     seg_tree(int,bool); seg_tree(int,const vll&,bool); 
  64.     const ll query(int,int); const void update(int,int,ll);
  65. };
  66.  
  67. seg_tree::seg_tree(int siz,bool indx=0) : n(siz),indx(indx){
  68.     st.resize(siz*4+1,reset); lazy.resize(siz*4+1,reset);
  69. }
  70.  
  71. seg_tree::seg_tree(int siz,const vll &a,bool indx=0) : n(siz),indx(indx){
  72.     st.resize(siz*4+1,reset); lazy.resize(siz*4+1,reset);
  73.     createTree(indx,n-1+indx,0,a);
  74. }
  75.  
  76. void seg_tree::createTree(int l,int r,int i,const vll &a){
  77.     if(l == r){
  78.         st[i] = a[l]; return;
  79.     }
  80.     int mid = (r-l)/2 + l;
  81.     createTree(l,mid,i*2+1,a); createTree(mid+1,r,i*2+2,a);
  82.     st[i] = merge_operation(st[i*2+1],st[i*2+2]);
  83. }
  84.  
  85. void seg_tree::lazyPush(int i,int l,int r){}
  86.  
  87. const ll seg_tree::query(int l,int r){
  88.     return query(indx,n-1+indx,0,l,r);
  89. }
  90.  
  91. ll seg_tree::query(int l,int r,int i,const int &tl,const int &tr){
  92.     if(r < tl || l > tr) return reset;
  93.     if(l >= tl && r <= tr) return st[i];
  94.     int mid = (r-l)/2 + l;
  95.     lazyPush(i,l,r);
  96.     return merge_operation(query(l,mid,i*2+1,tl,tr),query(mid+1,r,i*2+2,tl,tr));
  97. }
  98.  
  99. const void seg_tree::update(int l,int r,ll val){
  100.     assert(l == r); // remove if lazy
  101.     // current implementation is not lazy
  102.     update(indx,n-1+indx,0,val,l,r);
  103. }
  104.  
  105. void seg_tree::update(int l,int r,int i,const ll &val,const int& tl,const int& tr){
  106.     if(r < tl || l > tr) return;
  107.     if(l >= tl && r <= tr) {st[i] = val; return; }
  108.     int mid = (r-l)/2 + l;
  109.     lazyPush(i,l,r);
  110.     update(l,mid,i*2+1,val,tl,tr); update(mid+1,r,i*2+2,val,tl,tr);
  111.     st[i] = merge_operation(st[i*2+1],st[i*2+2]);
  112. }   
  113. const bool tests = 1;
  114. void solve_case(){
  115.     ll n; cin>>n; adj.clear(); adj.resize(n+1);
  116.     ind.clear(); ind.resize(n+1);
  117.     for(int i=1;i<n;i++){
  118.         ll u,v; cin>>u>>v;
  119.         adj[u].pb(v); adj[v].pb(u);
  120.     } level.resize(n+1); level[0]=INT_MAX; cnt=0;
  121.     dfs(); seg_tree st(cnt,0);
  122.     ll q; cin>>q; vll vis(n+1,0);
  123.     while(q--){
  124.         ll j; cin>>j;
  125.         ll node = st.query(ind[j][0],ind[j].back());
  126.         if(node == 0){
  127.             cout<<"NO\n";
  128.         }
  129.         else cout<<"YES "<<node<<endl;
  130.         if(vis[j]) continue;
  131.         for(ll i:ind[j]) st.update(i,i,j);
  132.         vis[j]=1;
  133.     }
  134. }
  135.  
  136. int32_t main()
  137. {
  138.     #ifdef LOCAL
  139.         freopen("error.txt", "w", stderr);
  140.         clock_t clk = clock();
  141.     #endif
  142.     fast_az_fuk
  143.     ll testcase=1; if(tests) cin>>testcase;
  144.     cout<<fixed<<setprecision(10);
  145.     for(ll test=1;test<=testcase;test++)
  146.     {//cout<<"Case #"<<test<<": ";
  147.         solve_case();
  148.     }
  149.     #ifdef LOCAL
  150.         cerr << '\n'<<"Time (in s): " << double(clock() - clk) * 1.0 / CLOCKS_PER_SEC << '\n';
  151.     #endif
  152.     return 0;
  153. }
Runtime error #stdin #stdout #stderr 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/rVSAtc
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!