fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <iostream>
  4. #define Sa7afy_H333 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
  6. #define cin(v) for (auto&i:v) cin >> i;
  7. #define cout(v) for (auto&i:v) cout << i << " ";cout<<e;
  8. #include <algorithm>
  9. #include <vector>
  10. #define ll long long int
  11. #define e '\n'
  12. #define PI acos(-1)
  13. #define PHI (long double)1.61803398875 //golden ratio
  14. #define sin(a) sin((a)*PI/180)
  15. #define cos(a) cos((a)*PI/180)
  16. #define tan(a) tan((a)*PI/180)
  17. #define  eb emplace_back
  18. #define ones(x) __builtin_popcountll(x)
  19. #define all(v) v.begin(), v.end()
  20. #define allr(v) v.rbegin(), v.rend()
  21. #define pii pair<ll,ll>
  22. #define vi vector<int>
  23. #define vll vector<ll>
  24. #include <set>
  25. #include <deque>
  26. #define d2v vector<vector<int>>
  27. typedef pair<int,int> Pii;
  28. #define  pb push_back
  29.  
  30. const int mod = 1e9+7;
  31.  
  32. ll mult(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; }
  33. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  34. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
  35. int dx[]={1,0,-1,0,1,1,-1,-1};
  36. int dy[]={0,1,0,-1,1,-1,-1,1};
  37.  
  38.  
  39.  
  40. struct BIT{
  41.     vector<ll>tree;
  42.     BIT(int n) {
  43.         tree.resize(n + 1,0);
  44.     }
  45.     ll get(int x) {
  46.         ll res = 0;
  47.         while (x) {
  48.             res += tree[x];
  49.             x -= x & -x;
  50.         }
  51.         return res;
  52.     }
  53.  
  54.     void update (ll x,ll val) {
  55.         while (x < tree.size()) {
  56.             tree[x] += val;
  57.             x += x & -x;
  58.         }
  59.     }
  60.  
  61.     ll query(int l,int r) {
  62.         return get(r) - get(l - 1);
  63.     }
  64.  
  65. };
  66.  
  67. const int N= 2e5+5;
  68. vector<ll>start(N),finish(N),val(N);
  69. vector<ll> adj[N];
  70. int timer ;
  71. BIT bit(N);
  72.  
  73. void dfs(int u,int p) {
  74.     start[u] = ++timer;
  75.     // get index for every node by flatten the tree
  76.     // update the node
  77.     bit.update(timer, val[u]);
  78.     for (auto x: adj[u]) {
  79.         if (x == p)continue;
  80.         dfs(x, u);
  81.     }
  82.     finish[u] = timer;
  83. }
  84.  
  85. void solve () {
  86.     int n, q, x, y, op;
  87.     cin >> n >> q;
  88.     for (int i = 1; i <= n; i++) {
  89.         cin >> val[i];
  90.     }
  91.     for (int i = 0; i < n - 1; i++) {
  92.         cin >> x >> y;
  93.         adj[x].eb(y);
  94.         adj[y].eb(x);
  95.     }
  96.     dfs(1,0);
  97.     while (q--) {
  98.         cin >> op;
  99.         if (op & 1) {
  100.             cin >> x >> y;
  101.             // update
  102.             bit.update(start[x], y-val[x]);
  103.             val[x] = y;
  104.         }else {
  105.             cin >> x;
  106.             cout << bit.query(start[x], finish[x]) << e;
  107.         }
  108.     }
  109. }
  110.  
  111. signed main() {
  112.     Sa7afy_H333
  113.     int tests = 1;
  114.    // cin >> tests;
  115.     for (int i = 1; i <= tests; i++) {
  116.         /*cout<<"Case #"<<i<<": ";*/
  117.         solve();
  118.     }
  119.     Time
  120. }
  121.  
Success #stdin #stdout #stderr 0.27s 40872KB
comments (?)
stdin 
5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3
stdout 
Standard output is empty
stderr 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/pCjgIy
language:
R (R 3.5.2)
created:
19 days 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!