fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int N = 100001;
  25. const int B = 400;
  26. const int SHIFT = N;
  27.  
  28. ll cnt[N*2/B + 3][2*N];
  29. int add[N*2/B + 3];
  30. int a[N*2/B + 3][B+1];
  31. int s[N];
  32. int e[N];
  33. vi adj[N+1];
  34. ll c[N+1];
  35. ll v[2*N+1];
  36. bool mode[N+1];
  37. int timer;
  38.  
  39. void dfs(int u, int p)
  40. {
  41. 	s[u] = timer++;
  42. 	v[s[u]] = c[u];
  43. 	for(int i = 0; i < adj[u].size(); i++)
  44. 	{
  45. 		int v = adj[u][i];
  46. 		if(p==v) continue;
  47. 		dfs(v, u);
  48. 	}
  49. 	e[u] = timer++;
  50. 	v[e[u]] = c[u];
  51. }
  52.  
  53. ii getindex(int x)
  54. {
  55. 	return mp(x/B, x%B);
  56. }
  57.  
  58. void init(int n)
  59. {
  60. 	for(int i = 0; i < n; i++)
  61. 	{
  62. 		ii l = getindex(s[i]); ii r = getindex(e[i]);
  63. 		cnt[l.fi][SHIFT] += c[i];
  64. 		cnt[r.fi][SHIFT] += c[i];
  65. 	}
  66. }
  67.  
  68. void upd(int l, int r, int ad)
  69. {
  70. 	//cerr<<l<<' '<<r<<' '<<ad<<'\n';
  71. 	int bl = l/B;
  72. 	int curpos = l%B;
  73. 	int cur = l;
  74. 	for(;(curpos < B && cur<=r); cur++,curpos++)
  75. 	{
  76. 		int val = a[bl][curpos];
  77. 		cnt[bl][val+SHIFT]-=v[cur];
  78. 		cnt[bl][val+ad+SHIFT]+=v[cur];
  79. 		a[bl][curpos]+=ad;
  80. 	}
  81. 	curpos = 0;
  82. 	bl++;
  83. 	while(cur+B-1<=r)
  84. 	{
  85. 		add[bl] += ad;		
  86. 		bl++;
  87. 		cur+=B;
  88. 	}
  89. 	for(;(curpos < B && cur<=r); cur++,curpos++)
  90. 	{
  91. 		int val = a[bl][curpos];
  92. 		cnt[bl][val+SHIFT]-=v[cur];
  93. 		cnt[bl][val+ad+SHIFT]+=v[cur];
  94. 		a[bl][curpos]+=ad;
  95. 	}
  96. }
  97.  
  98. ll query(int l, int r, int vv)
  99. {
  100. 	//cerr<<l<<' '<<r<<' '<<vv<<'\n';
  101. 	ll ans = 0;
  102. 	int bl = l/B;
  103. 	int curpos = l%B;
  104. 	int cur = l;
  105. 	for(;(curpos < B && cur<=r); cur++,curpos++)
  106. 	{
  107. 		int val = a[bl][curpos];
  108. 		if(val+add[bl]==vv) ans+=v[cur];
  109. 	}
  110. 	curpos = 0;
  111. 	bl++;
  112. 	while(cur+B-1<=r)
  113. 	{
  114. 		ans+=cnt[bl][SHIFT-add[bl]+vv];	
  115. 		bl++;
  116. 		cur+=B;
  117. 	}
  118. 	for(;(curpos < B && cur<=r); cur++,curpos++)
  119. 	{
  120. 		int val = a[bl][curpos];
  121. 		if(val+add[bl]==vv) ans+=v[cur];
  122. 	}
  123. 	return ans;
  124. }
  125.  
  126. void flip(int u)
  127. {
  128. 	if(mode[u])
  129. 	{
  130. 		upd(s[u], e[u], -1);
  131. 	}
  132. 	else
  133. 	{
  134. 		upd(s[u], e[u], 1);
  135. 	}
  136. 	mode[u]^=1;
  137. }
  138.  
  139. ll query(int u)
  140. {
  141. 	if(!mode[u]) return 0;
  142. 	else return query(s[u], e[u], a[s[u]/B][s[u]%B]+add[s[u]/B])/2;
  143. }
  144.  
  145. int main()
  146. {
  147. 	ios_base::sync_with_stdio(0); cin.tie(0);
  148. 	int n; cin >> n;
  149. 	timer=0;
  150. 	for(int i = 0; i < n; i++)
  151. 	{
  152. 		cin>>c[i];
  153. 		mode[i]=1;
  154. 	}
  155. 	for(int i = 0; i < n - 1; i++)
  156. 	{
  157. 		int u, v; cin>>u>>v;
  158. 		u--; v--;
  159. 		adj[u].pb(v); adj[v].pb(u);
  160. 	}
  161. 	dfs(0, -1);
  162. 	init(n);
  163. 	int q; cin >> q;
  164. 	while(q--)
  165. 	{
  166. 		int t, u; cin>>t>>u;
  167. 		t--; u--;
  168. 		if(t==0)
  169. 		{
  170. 			flip(u);
  171. 		}
  172. 		else
  173. 		{
  174. 			cout<<query(u)<<'\n';
  175. 		}
  176. 	}
  177. }
  178.  
Success #stdin #stdout 0s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8px5uW
language:
C++14 (gcc 8.3)
created:
6 years 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!