fork download
copy 
  1. //tonynater
  2.  
  3. #include <iostream>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. typedef long long ll;
  9.  
  10. const ll mod = 1000000007;
  11.  
  12. const int maxn = 200010;
  13.  
  14. int v[maxn], q, n = 1, qstore[maxn][2]; //input
  15.  
  16. int parent[maxn]; //tree
  17. vector<int> children[maxn]; //tree
  18.  
  19. int curtravpos, traversal[maxn], bounds[maxn][2]; //traversal
  20.  
  21. int activechildren[maxn]; //processing
  22.  
  23. void dfs(int u) {
  24.     traversal[curtravpos] = u;
  25.     bounds[u][0] = curtravpos;
  26.     ++curtravpos;
  27.     for(auto v : children[u]) {
  28.         dfs(v);
  29.     }
  30.     bounds[u][1] = curtravpos-1;
  31. }
  32.  
  33. struct segment_tree {
  34.     int b, e;
  35.     segment_tree *lst, *rst;
  36.  
  37.     int sum;
  38.     ll mult;
  39.  
  40.     segment_tree(int _b, int _e) {
  41.         b = _b;
  42.         e = _e;
  43.         sum = 0;
  44.         mult = 1;
  45.         lst = rst = NULL;
  46.         if(b < e) {
  47.             lst = new segment_tree(b,(b+e)/2);
  48.             rst = new segment_tree((b+e)/2+1,e);
  49.             merge();
  50.         }
  51.     }
  52.  
  53.     void prop() {
  54.         if(mult > 1) {
  55.             sum = sum*mult%mod;
  56.             if(lst != NULL) {
  57.                 lst->mult = lst->mult*mult%mod;
  58.                 rst->mult = rst->mult*mult%mod;
  59.             }
  60.             mult = 1;
  61.         }
  62.     }
  63.  
  64.     void merge() {
  65.         if(lst != NULL) {
  66.             sum = (lst->sum+rst->sum)%mod;
  67.         }
  68.     }
  69.  
  70.     void rmult(int l, int r, int m) {
  71.         if(m == 1) {
  72.             return;
  73.         }
  74.         prop();
  75.         if(e < l || r < b) {
  76.             return;
  77.         }else if(l <= b && e <= r) {
  78.             mult = m;
  79.             prop();
  80.         }else {
  81.             lst->rmult(l,r,m);
  82.             rst->rmult(l,r,m);
  83.             merge();
  84.         }
  85.     }
  86.  
  87.     void set(int idx, int v) {
  88.         prop();
  89.         if(b == idx && idx == e) {
  90.             sum = v;
  91.         }else if(idx <= (b+e)/2) {
  92.             lst->set(idx,v);
  93.             rst->prop();
  94.             merge();
  95.         }else {
  96.             lst->prop();
  97.             rst->set(idx,v);
  98.             merge();
  99.         }
  100.     }
  101.  
  102.     int get(int l, int r) {
  103.         prop();
  104.         if(e < l || r < b) {
  105.             return 0;
  106.         }else if(l <= b && e <= r) {
  107.             return sum;
  108.         }else {
  109.             int lsum = lst->get(l,r);
  110.             int rsum = rst->get(l,r);
  111.             return (lsum+rsum)%mod;
  112.         }
  113.     }
  114. };
  115.  
  116. ll binpow(ll base, int exp) {
  117.     if(exp == 0) {
  118.         return 1;
  119.     }else {
  120.         ll half = binpow(base,exp/2);
  121.         ll full = half*half%mod;
  122.         if(exp%2) {
  123.             full = full*base%mod;
  124.         }
  125.         return full;
  126.     }
  127. }
  128.  
  129. int main() {
  130.     ios_base::sync_with_stdio(0);
  131.     cin.tie(NULL);
  132.  
  133.     cin >> v[0] >> q;
  134.  
  135.     for(int i = 0; i < q; i++) {
  136.         cin >> qstore[i][0] >> qstore[i][1];
  137.         --qstore[i][1];
  138.         if(qstore[i][0] == 1) {
  139.             parent[n] = qstore[i][1];
  140.             cin >> v[n];
  141.             children[parent[n]].push_back(n);
  142.             qstore[i][1] = n;
  143.             ++n;
  144.         }
  145.     }
  146.  
  147.     dfs(0);
  148.  
  149.     segment_tree *st_root = new segment_tree(0,n-1);
  150.     st_root->set(0,v[0]);
  151.  
  152.     for(int i = 0; i < q; i++) {
  153.         int x = qstore[i][1];
  154.         if(qstore[i][0] == 1) {
  155.             int par = parent[x];
  156.             int lb = bounds[par][0], rb = bounds[par][1];
  157.             int curchildren = ++activechildren[par];
  158.             int mult = binpow(curchildren,mod-2)*(curchildren+1)%mod;
  159.             st_root->rmult(lb,rb,mult);
  160.  
  161.             int parmultfactor = st_root->get(lb,lb)*binpow(v[par],mod-2)%mod;
  162.             int childval = ll(parmultfactor)*v[x]%mod;
  163.             st_root->set(bounds[x][0],childval);
  164.         }else {
  165.             int rootres = st_root->get(bounds[x][0],bounds[x][1]);
  166.             int scale = 1;
  167.             if(x > 0) {
  168.                 scale = st_root->get(bounds[parent[x]][0],bounds[parent[x]][0])
  169.                             *binpow(v[parent[x]],mod-2)%mod;
  170.             }
  171.             int res = rootres*binpow(scale,mod-2)%mod;
  172.             cout << res << '\n';
  173.         }
  174.     }
  175.  
  176.     return 0;
  177. }
  178.  
Success #stdin #stdout 0.01s 12080KB
comments (?)
stdin
copy 
2 5
1 1 3
1 2 5
1 3 7
1 4 11
2 1
stdout
copy 
344
https://ideone.com/pObeIV
language:
C++14 (gcc 8.3)
created:
9 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!