fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<utility>
  5.  
  6. using namespace std;
  7.  
  8. #define FOR(i , a , n) for(int (i) = (a); (i) < (int)(n);++(i))
  9. #define pb push_back
  10. #define sz( x ) (int)(x).size()
  11. #define mp make_pair
  12. typedef long long ll;
  13.  
  14. struct node
  15. {
  16.   ll val;
  17.   ll odd , even;
  18.   node *right , *left;
  19.   node()
  20.   {
  21.     right = left = NULL;
  22.     val = 0;
  23.     odd = 0;
  24.     even = 0;
  25.   }
  26. };
  27. node *root;
  28. const int maxN = 2e5 + 100;
  29. vector<int> G[maxN] , nv , ls , oe;
  30. vector<ll> v;
  31. int n , m , curmark = 0 ;
  32. bool vis[maxN];
  33. inline void add(node *cur, int fi , int se , int l , int r,ll val , int num)
  34. {
  35.   int mid = (fi + se) / 2;
  36.   if(cur->left == NULL) cur->left = new node();
  37.   if(cur->right == NULL) cur->right = new node();
  38.   if(fi == l and se == r) ((num) ? cur->odd += val : cur->even += val);   
  39.   else if(r <= mid) add(cur->left , fi , mid , l , r , val , num);
  40.   else if(mid < l) add(cur->right , mid + 1 , se , l , r , val , num);
  41.   else
  42.     {
  43.       add(cur->left , fi , mid , l , mid , val , num);
  44.       add(cur->right , mid + 1 , se , mid + 1 , r , val , num); 
  45.     } 
  46. } 
  47. inline pair<ll,ll> query(node *cur , int fi , int se , int now)
  48. {
  49.   if(cur->left == NULL) cur->left = new node();
  50.   if(cur->right == NULL) cur->right = new node();
  51.   pair<ll,ll>  p;
  52.   p.first += cur->even;
  53.   p.second += cur->odd; 
  54.   if(fi == se and fi == now)
  55.     {
  56.       return make_pair(p.first , p.second); 
  57.     } 
  58.   else
  59.     {
  60.       int mid = (fi + se) / 2;
  61.       if(now <= mid) return query(cur->left , fi , mid , now);
  62.       else return query(cur->right , mid + 1 , se , now);
  63.     }
  64. } 
  65. inline void dfs(int u , int dis)
  66. {
  67.   vis[u] = true;
  68.   nv[u] = curmark;
  69.   curmark++; 
  70.   oe[u] = dis % 2;
  71.   FOR(i , 0 , sz(G[u])) if(!vis[G[u][i]])  dfs(G[u][i] , dis + 1);
  72.   ls[u] = curmark - 1;
  73. }  
  74. int main()
  75. {
  76.   ios_base::sync_with_stdio(0);
  77.   cin>> n >> m;
  78.   v.resize(n);
  79.   nv.resize(n);
  80.   ls.resize(n);
  81.   oe.resize(n);
  82.   //FOR(i , 0 , n) cin >> v[i];
  83.   FOR(i , 0 , n - 1)
  84.     {
  85.       int x , y;
  86.       cin >> x >> y;
  87.       x-- , y--;
  88.       G[x].pb(y);
  89.       G[y].pb(x);
  90.     }
  91.   dfs(0 , 0);
  92.   for(int i = 0 ; i < m ; i++)
  93.     {
  94.       int tp , x ;
  95.       ll y;
  96.       cin>> x >> y;
  97.       FOR(i , 0 , n)
  98. 	{
  99. 	  pair<ll,ll> p = query(root ,0 , n-1 , nv[x]);
  100. 	  if(oe[nv[x]]) swap(p.first , p.second);
  101. 	  cout << p.first<<' ' << p.second <<' '<<v[nv[x]]<< endl;
  102. 	}
  103.     }
  104.   /*
  105.   root = new node();
  106.   FOR(i , 0 , m)
  107.     {
  108.       int tp , x ;
  109.       ll y;
  110.       cin >> tp >> x;
  111.       x--;
  112.       if(tp == 2)
  113. 	{
  114. 	  pair<ll,ll> p = query(root ,0 , n-1 , nv[x]);
  115. 	  if(oe[nv[x]]) swap(p.first , p.second);
  116. 	  cout << p.first<<' ' << p.second <<' '<<v[nv[x]]<< endl;
  117. 	}
  118.       else
  119. 	{
  120. 	  cin >> y;
  121. 	  add(root , 0 , n-1 , nv[x] , ls[x] , y , oe[x]);
  122. 	}
  123.  
  124.     }
  125.   */
  126.   return 0;
  127. }
  128.  
Runtime error #stdin #stdout 0s 6032KB
comments (?)
stdin
copy 
4 1
1 2
2 3
2 4
1 3
stdout
copy 
Standard output is empty
https://ideone.com/jfVNiS
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!