fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 1000001
  14. #define Bit(i) (1LL << i )
  15. #define INF (1ll<<60)
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q ;
  21. ll a[MAXN] ;
  22. ll st[MAXN], fin[MAXN], timeDFS ;
  23. vector<ll> adj[MAXN ] ;
  24.  
  25. struct Seg {
  26.     ll val[MAXN << 2 ] ;
  27.     ll lazy[MAXN << 2 ] ;
  28.  
  29.     void fix(ll id, ll l, ll r ) {
  30.         if(lazy[id]== 0 ) return ;
  31.         val[id] += (lazy[id]) * (r - l + 1) ;
  32.         if(l != r ) {
  33.             lazy[id << 1] += lazy[id] ;
  34.             lazy[id << 1 | 1 ] += lazy[id];
  35.         }
  36.         lazy[id] = 0 ;
  37.     }
  38.  
  39.     void update(ll id, ll l,ll r, ll u, ll v, ll value ) {
  40.         fix(id, l, r ) ;
  41.         if(u > r || v < l ) return ;
  42.         if(u <= l && v >= r ) {
  43.             lazy[id] += value ;
  44.             fix(id, l,r ) ;
  45.             return ;
  46.         }
  47.         ll m = l + r >> 1 ;
  48.         update(id << 1, l, m, u, v, value ) ;
  49.         update(id << 1 | 1, m + 1, r, u, v, value ) ;
  50.         val[id] = val[id << 1] + val[id << 1 | 1 ] ;
  51.     }
  52.  
  53.     ll get(ll id, ll l, ll r, ll u, ll v ) {
  54.         fix(id, l, r ) ;
  55.         if(u > r || v < l ) return 0 ;
  56.         if(u <=l && v >= r ) return val[id] ;
  57.         ll m = l + r >> 1 ;
  58.         return get(id << 1, l, m, u, v ) + get(id << 1 | 1, m  + 1, r, u, v ) ;
  59.     }
  60. } seg ;
  61.  
  62.  
  63. void dfs(ll u, ll p ) {
  64.     st[u] = ++ timeDFS ;
  65.     for(ll v : adj[u]) if(v != p ) {
  66.             dfs(v, u ) ;
  67.         }
  68.     fin[u] = timeDFS ;
  69. }
  70.  
  71. void init() {
  72.     cin >> n >> q ;
  73.     FOR(i, 1, n ) cin >> a[i] ;
  74.     FOR(i, 2, n ) {
  75.         ll x,  y ;
  76.         cin >> x >> y ;
  77.         adj[x].push_back(y) ;
  78.         adj[y].push_back(x) ;
  79.     }
  80. }
  81.  
  82. void solve() {
  83.     dfs(1 , 1 ) ;
  84.     FOR(i, 1, n ) {
  85.         seg.update(1, 1, n, st[i], st[i], a[i]);
  86.     }
  87. //    debug(seg.val[1]) ;
  88.     FOR(cnt, 1, q ) {
  89.         ll t, u, x ;
  90.         cin >> t >> u ;
  91.         if(t == 1 ) {
  92.             cin >> x ;
  93.             seg.update(1, 1, n, st[u], fin[u], x ) ;
  94.         } else cout << seg.get(1, 1, n, st[u], fin[u]) << el ;
  95.     }
  96. }
  97.  
  98.  
  99. _ROOT_ {
  100. //    freopen(NAME".inp", "r", stdin);
  101. //    freopen(NAME".out", "w", stdout) ;
  102.     ios_base::sync_with_stdio(0);
  103.     cin.tie(0);
  104.     cout.tie(0);
  105.     int t = 1; // cin >> t ;
  106.     while(t--) {
  107.         init();
  108.         solve();
  109.     }
  110.     return (0&0);
  111. }
  112.  
Success #stdin #stdout 0.01s 30132KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i039ad
language:
C++14 (gcc 8.3)
created:
1 day 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!