fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define fi first
  4. #define se second
  5.  
  6. #define For(i, a, b) for (int i = (a); i <= (b); ++i)
  7. #define ForD(i, a, b) for (int i = (a); i >= (b); --i)
  8. #define rep(i, n) for (int i = 0; i < (n); ++i)
  9. #define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
  10. #define coutE(x) {cout << x << '\n'; return;}
  11. #define pb push_back
  12. #define pf push_front
  13.  
  14. #define all(x) x.begin(), x.end()
  15. #define bs binary_search
  16. #define ub upper_bound
  17. #define lb lower_bound
  18.  
  19. #define endl '\n'
  20.  
  21. #define db long double
  22. #define ll long long
  23. #define ii pair<int, int>
  24. #define vi vector<int>
  25. #define vii vector<ii>
  26.  
  27. #define int long long
  28.  
  29.  
  30. using namespace std;
  31.  
  32. void file(string s){
  33.  
  34.     if (s.empty()) return;
  35.  
  36.     freopen((s + ".inp").c_str(), "r", stdin);
  37.     freopen((s + ".out").c_str(), "w", stdout);
  38. }
  39.  
  40. template <class X, class Y>
  41. 	bool minimize(X &x, Y y){
  42. 		if (x > y){
  43. 			x = y;
  44. 			return 1;
  45. 		}
  46.  
  47. 		return 0;
  48. 	}
  49.  
  50. template <class X, class Y>
  51. 	bool maximize(X &x, Y y){
  52. 		if (x < y){
  53. 			x = y;
  54. 			return 1;
  55. 		}
  56.  
  57. 		return 0;
  58. 	}
  59.  
  60.  
  61. mt19937_64 rng(time(0));
  62.  
  63. const int N = 1e6 + 5;
  64.  
  65. const int MOD = 1e9 + 7; //998244353;
  66. const int INF = 1e9;
  67. const long long LINF = 1e18;
  68.  
  69. const int dx[] = {1, 0, 0, -1};
  70. const int dy[] = {0, 1, -1, 0};
  71.  
  72. int n, q, a[N];
  73. vi g[N];
  74. int in[N], out[N], timer, node[N];
  75.  
  76.  
  77. struct SigmaTree{
  78.  
  79. 	int st[2 * N];
  80.  
  81. 	void build(){
  82.  
  83. 		For(i, 1, n) st[i + n - 1] = a[node[i]];
  84. 		ForD(i, n - 1, 1) st[i] = st[i << 1] + st[i << 1 | 1];
  85. 	}
  86.  
  87. 	void update(int p, int x){
  88.  
  89. 		p += n - 1;
  90. 		st[p] = x;
  91.  
  92. 		while (p > 1){
  93. 			st[p >> 1] = st[p] + st[p ^ 1];
  94. 			p >>= 1;
  95. 		}
  96. 	}
  97.  
  98. 	int get(int l, int r){
  99.  
  100. 		l += n - 1; r += n - 1;
  101. 		int res = 0;
  102. 		while (l <= r){
  103. 			if (l & 1) res += st[l++];
  104. 			if (!(r & 1)) res += st[r--];
  105.  
  106. 			l >>= 1; r >>= 1;
  107. 		}
  108.  
  109. 		return res;
  110. 	}
  111. } ST;
  112.  
  113. void dfs(int u, int prev = 0){
  114. 	in[u] = ++timer;
  115. 	node[timer] = u;
  116.  
  117. 	for (int v: g[u]) if (v != prev){
  118. 		dfs(v, u);
  119. 	}
  120.  
  121. 	out[u] = timer;
  122. }
  123.  
  124. void solve(){
  125.  
  126. 	cin >> n >> q;
  127. 	For(i, 1, n) cin >> a[i];
  128. 	rep(i, n - 1){
  129. 		int u, v; cin >> u >> v;
  130. 		g[u].pb(v); g[v].pb(u);
  131. 	}
  132.  
  133. 	dfs(1);
  134. 	ST.build();
  135.  
  136. 	while (q--){
  137. 		int t; cin >> t;
  138. 		if (t == 1){
  139. 			int s, x; cin >> s >> x;
  140. 			ST.update(in[s], x);
  141. 		}
  142. 		else{
  143. 			int s; cin >> s;
  144. 			cout << ST.get(in[s], out[s]) << endl;
  145. 		}
  146. 	}
  147.  
  148.  
  149. }
  150.  
  151.  
  152. signed main(){
  153.  
  154. 	ios_base::sync_with_stdio(0); 
  155. 	cin.tie(0); cout.tie(0);
  156. 	file("");
  157.  
  158. 	int T = 1;
  159. 	//cin >> T;
  160. 	while (T--) solve();
  161.  
  162. 	return 0;
  163. }
Success #stdin #stdout 0.01s 34268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BYA9Tj
language:
C++14 (gcc 8.3)
created:
76 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!