SHARE
TWEET

Untitled

Bsher Jul 17th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     G : Game with Magnets
  3.     Saeed : DSU on tree
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9. int n,q,ans[100100];
  10. multiset<pair<int,int>> *s[100100];
  11. vector<pair<int,int>> v[100100], coin[100100];
  12. vector<int> G[100100], Q;
  13.  
  14. void DFS(int u, int p)
  15. {
  16.     int B = 0;
  17.     for(auto v : G[u]) if( v != p )
  18.     {
  19.         DFS(v,u);
  20.         if( !B || s[B]->size() < s[v]->size() )
  21.             B = v;
  22.     }
  23.    
  24.     if( !B )
  25.         s[u] = new multiset<pair<int,int>>;
  26.     else s[u] = s[B];
  27.  
  28.     for (auto i : coin[u])
  29.         s[u]->insert(i);
  30.  
  31.     for(auto v : G[u])
  32.         if( v != B && v != p )
  33.             for (auto x : *s[v])
  34.                 s[u]->insert(x);
  35.    
  36.     vector<pair<int, int>> d;
  37.     for (auto i : v[u])
  38.     {
  39.         auto it = s[u]->lower_bound(make_pair(i.first, 0));
  40.        
  41.         while(it != s[u]->end() && it->first <= i.second){
  42.             ans[it->second] = u;
  43.             d.push_back(*it);
  44.             it++;
  45.         }
  46.     }
  47.  
  48.     for (auto i : d)
  49.         s[u]->erase(i);
  50. }
  51.  
  52. int main()
  53. {
  54.     ios::sync_with_stdio(0);
  55.     cin.tie(0); cout.tie(0);
  56.  
  57.     int T;  cin >> T;
  58.     while(T--){
  59.         Q.clear();
  60.  
  61.         cin >> n;
  62.         int T_T; cin >> T_T;
  63.  
  64.         for (int i = 0; i <= n; i++)
  65.         {
  66.             G[i].clear();
  67.             v[i].clear();
  68.             coin[i].clear();
  69.             s[i] = NULL;
  70.         }
  71.  
  72.  
  73.         for (int i = 1; i < n; i++)
  74.         {
  75.             int a;  cin >> a;
  76.             int b;  cin >> b;
  77.            
  78.             G[a].push_back(b);
  79.             G[b].push_back(a);
  80.         }
  81.  
  82.         for (int i = 1; i <= T_T; i++)
  83.         {
  84.             int t;  cin >> t;
  85.  
  86.             ans[i] = -1;
  87.  
  88.             if (t == 1){
  89.                 int u;  cin >> u;
  90.                 int t1; cin >> t1;
  91.                 int t2; cin >> t2;
  92.  
  93.                 v[u].push_back({t1, t2});
  94.             }else{
  95.                 int u;  cin >> u;
  96.                 int t1; cin >> t1;
  97.            
  98.                 coin[u].push_back({t1, i});
  99.                 Q.push_back(i);
  100.             }
  101.         }
  102.  
  103.         DFS(1, 0);
  104.  
  105.         for (auto i : Q)
  106.             cout << ans[i] << '\n';
  107.  
  108.     }
  109.  
  110.     return 0;
  111. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top