fork download
copy 
  1. // I can't tell you what it really is,
  2. // I can only tell you what it feels like.
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5.  
  6. // #define int long long
  7. #define F first
  8. #define S second
  9. #define sz(x) ((int)x.size())
  10. #define rep(i,a,n) for (int i = a; i <= n; ++i)
  11. #define all(v)  v.begin(), v.end()
  12. #define pb push_back
  13. #define P pair < int, int >
  14. #define E cout << '\n'
  15. typedef long long lll;
  16.  
  17. const int mod = 1e9 + 7;
  18. const int N = 3e5 + 5;
  19.  
  20. vector < int > v[N];
  21. int val[N], idx[N], ar[N];
  22. int dist[N], ok = 1;
  23. int sz[N], a[N];
  24.  
  25. void dfs(int x, int p, int lev) {
  26.     ar[ok] = x;
  27.     idx[x] = ok++;
  28.     sz[x] = 1;
  29.     dist[x] = lev;
  30.     for (int i : v[x]) {
  31.         if (i != p) {
  32.             dfs(i, x, lev + 1);
  33.             sz[x] += sz[i];
  34.         }
  35.     }
  36. }
  37.  
  38. vector < int > ind[N];
  39. vector < lll > bit[N];
  40.  
  41. void update(int r, int c, int val) { 
  42.     while (c != 0 && c < sz(bit[r])) {
  43.         bit[r][c] += val;
  44.         c += c & -c;        
  45.     }    
  46. }
  47.  
  48. lll get(int r, int c) {
  49.     lll ans = 0;
  50.     // assert(c <= bit[r].size());
  51.     while (c > 0) {
  52.         ans += bit[r][c];
  53.         c -= c&-c;
  54.     }
  55.     return ans;
  56. }
  57.  
  58.  
  59. inline void solve() {
  60.    int n, l, r;
  61.    cin >> n;
  62.    rep(i,2,n) {
  63.        cin >> l >> r;       
  64.        v[l].pb(r);
  65.        v[r].pb(l);
  66.    }
  67.    dfs(1, 1, 0);
  68.    rep(i,1,n) {
  69.        cin >> l;
  70.        a[idx[i]] = l;       
  71.    }
  72.    rep(i,0,n) {
  73.        ind[i].push_back(0);
  74.    }
  75.    rep(i,1,n) {      
  76.        ind[dist[ar[i]]].push_back(i);
  77.    }
  78.    rep(i,0,n) {
  79.        if (ind[i].size() < 2) {
  80.                continue;
  81.        }
  82.        bit[i].resize(sz(ind[i]));    
  83.        for (int j = 1; j < ind[i].size(); ++j) {
  84.            assert(bit[i].size() <= sz(ind[i]));
  85.            update(i, j, a[ind[i][j]]);           
  86.        }
  87.    }   
  88.    int q, f;
  89.    cin >> q;
  90.    while (q--) {
  91.        cin >> f >> l >> r;
  92.        if (f == 1) {
  93.            int index = idx[l];
  94.            assert(l>=1 && l<=n);
  95.            int distance = dist[l];
  96.            int bitMeIndex = lower_bound(all(ind[distance]), index) - ind[distance].begin(); 
  97.            assert(index == ind[distance][bitMeIndex]);
  98.            update(distance, bitMeIndex, -a[index]+r);           
  99.            a[index] = r;
  100.        }
  101.        else {
  102.            int distNow = r + dist[l];           
  103.            if (bit[distNow].size() < 2) {
  104.                cout << "0\n";
  105.                continue;
  106.            }
  107.            int lindex = idx[l], rindex = idx[l] + sz[l] - 1;
  108.            lll ans = 0;           
  109.            if (lindex <= rindex) {
  110.                int ll = lower_bound(all(ind[distNow]), lindex) - ind[distNow].begin();
  111.                int rr = upper_bound(ind[distNow].begin()+ll, ind[distNow].end(), rindex) - ind[distNow].begin();
  112.                if (ll < rr) {
  113.                    ans = get(distNow, rr-1) - get(distNow, ll-1);
  114.                }
  115.            }
  116.            cout << ans << '\n';
  117.        }
  118.    }
  119. }
  120. signed main() {
  121.   ios_base::sync_with_stdio(0);
  122.   cin.tie(NULL);
  123.   cout.tie(NULL);
  124.   int t = 1;
  125.   //cin >> t; while(t--)
  126.   solve();
  127.   return 0;
  128. }
Runtime error #stdin #stdout 0.01s 24380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/I2VdJq
language:
C++14 (gcc 8.3)
created:
4 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!