fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define sd(x) scanf("%lld",&x)
  4. #define sd2(x,y) scanf("%lld%lld",&x,&y)
  5. #define sd3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
  6.  
  7. #define fi first
  8. #define se second
  9. #define pb push_back
  10. #define mp make_pair
  11. #define foreach(it, v) for(__typeof((v).begin()) it=(v).begin(); it != (v).end(); ++it)
  12. #define meta __FUNCTION__,__LINE__
  13.  
  14. #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  15. #define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef pair<ll,ll> pii;
  21.  
  22. template<typename S, typename T> 
  23. ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;}
  24.  
  25. template<typename T>
  26. ostream& operator<<(ostream& out,vector<T> const& v){
  27. ll l=v.size();for(ll i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;}
  28.  
  29. void tr(){cout << endl;}
  30. template<typename S, typename ... Strings>
  31. void tr(S x, const Strings&... rest){cout<<x<<' ';tr(rest...);}
  32.  
  33. const ll LOGN = 19;
  34. const ll N = 1 << LOGN;
  35. const ll INF = 1ll << 40;
  36.  
  37. ll n, q, A, B, P;
  38.  
  39. vector<ll> g[N];
  40. ll c[N];
  41.  
  42. ll indx;
  43. ll baseArray[N], chainHead[N], pos[N], chain[N], sz[N], chain_no;
  44. ll p[LOGN][N], lvl[N];
  45.  
  46. int vis[N];
  47.  
  48. struct node{
  49. 	ll cnt, maxval, lazy;
  50.  
  51. 	node(){
  52. 		cnt = maxval = lazy = 0;
  53. 	}
  54.  
  55. 	void assign(ll value){
  56. 		lazy = 0;
  57. 		maxval = value;
  58. 		cnt = (maxval < P)? 1 : 0;
  59. 	}
  60.  
  61. 	void update(ll value){
  62. 		maxval += value, lazy += value;
  63. 	}
  64.  
  65. 	void combine(node &left, node &right){
  66. 		maxval = max(left.maxval, right.maxval) + lazy;
  67. 		cnt = left.cnt + right.cnt;
  68. 	}
  69.  
  70. } tree[2*N];
  71.  
  72. void build(ll id = 1, ll l = 0, ll r = n){
  73. 	if(l+1 == r){
  74. 		tree[id].assign(baseArray[l]);
  75. 		return;
  76. 	}
  77.  
  78. 	ll left = id << 1, right = left + 1, mid = (l + r) >> 1;
  79.  
  80. 	tree[id].lazy = 0;	
  81. 	build(left, l, mid); build(right, mid, r);
  82.  
  83. 	tree[id].combine(tree[left], tree[right]);
  84. 	return;
  85. }
  86.  
  87. void updateSegTree(ll x, ll y, ll val, ll id = 1, ll l = 0, ll r = n){
  88. 	if(x >= r or l >= y or x >= y) return;
  89. 	if(x <= l and r <= y){
  90. 		tree[id].update(val);
  91. 		return;
  92. 	}
  93.  
  94. 	ll left = id << 1, right = left+1, mid = (l+r) >> 1;
  95.  
  96. 	updateSegTree(x, y, val, left, l, mid); 
  97. 	updateSegTree(x, y, val, right, mid, r);
  98.  
  99. 	tree[id].combine(tree[left], tree[right]);
  100. }
  101.  
  102. void propagateSegTree(ll id, ll x, ll y, ll lazy){
  103. 	if(tree[id].maxval + lazy < P or !tree[id].cnt){
  104. 		tree[id].update(lazy);
  105. 		return;
  106. 	}
  107.  
  108. 	if(x+1 == y){
  109. 		if(tree[id].maxval + lazy >= P) tree[id].maxval = -INF, tree[id].cnt = 0;
  110. 		return;
  111. 	}
  112.  
  113. 	lazy += tree[id].lazy;
  114. 	tree[id].lazy = 0;
  115.  
  116. 	ll left = id << 1, right = left + 1, mid = (x+y) >> 1;
  117.  
  118. 	propagateSegTree(left, x, mid, lazy);
  119. 	propagateSegTree(right, mid, y, lazy);
  120.  
  121. 	tree[id].combine(tree[left], tree[right]);
  122. }
  123.  
  124. ll querySegTree(ll x, ll y, ll id = 1, ll l = 0, ll r = n, ll lazy = 0){
  125. 	tree[id].update(lazy);
  126. 	if(x >= r or l >= y or x >= y) return 0;
  127.  
  128. 	if(x <= l and r <= y){
  129. 		propagateSegTree(id, l, r, 0);
  130. 		return r - l - tree[id].cnt;
  131. 	}
  132.  
  133. 	ll left = id << 1, right = left+1, mid = (l+r) >> 1;
  134.  
  135. 	lazy = tree[id].lazy;
  136. 	tree[id].lazy = 0;
  137.  
  138. 	int ret = querySegTree(x, y, left, l, mid, lazy) + querySegTree(x, y, right, mid, r, lazy);
  139. 	tree[id].combine(tree[left], tree[right]);
  140. 	return ret;
  141. }
  142.  
  143. void dfs(ll cur, ll prev){
  144. 	vis[cur] = 1;
  145. 	sz[cur] = 1;
  146. 	foreach(it, g[cur]){
  147. 		if(*it == prev) continue;
  148. 		if(vis[*it]) continue;
  149.  
  150. 		lvl[*it] = lvl[cur] + 1;
  151. 		p[0][*it] = cur;
  152.  
  153. 		dfs(*it, cur);
  154. 		sz[cur] += sz[*it];
  155. 	}
  156. }
  157.  
  158. void heavyLightDecomposition(ll cur, ll prev){
  159. 	chain[cur] = chain_no, pos[cur] = ++indx;
  160. 	baseArray[indx] = c[cur];
  161.  
  162. 	ll heavy_child = -1, heavy_size = 0;
  163. 	foreach(it, g[cur]){
  164. 		if(*it == prev) continue;
  165.  
  166. 		if(sz[*it] > heavy_size){
  167. 			heavy_size = sz[*it];
  168. 			heavy_child = *it;
  169. 		}
  170. 	}
  171.  
  172. 	if(heavy_child != -1) heavyLightDecomposition(heavy_child, cur);
  173.  
  174. 	foreach(it, g[cur]){
  175. 		if(*it == prev or *it == heavy_child) continue;
  176.  
  177. 		chain_no++;
  178. 		chainHead[chain_no] = *it;
  179. 		heavyLightDecomposition(*it, cur);
  180. 	}	
  181. }
  182.  
  183. void preprocess(){
  184. 	for(ll i = 1; i < LOGN; i++)
  185. 		for(ll j = 1; j <= n; j++)
  186. 			p[i][j] = p[i-1][p[i-1][j]];
  187. }
  188.  
  189. ll LCA(ll x, ll y){
  190. 	if(lvl[x] < lvl[y]) swap(x,y);
  191.  
  192. 	ll tmp = 1; while((1 << tmp) <= lvl[x]) tmp++; tmp--;
  193.  
  194. 	for(ll i = tmp; i >= 0; i--) if(lvl[x] - (1<<i) >= lvl[y]) x = p[i][x];
  195. 	if(x == y) return y;
  196.  
  197. 	for(ll i = tmp; i >= 0; i--) if(p[i][x] > 0 and p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
  198. 	return p[0][x];
  199. }
  200.  
  201. void chainUpdate(ll x, ll y, ll w, ll flag){
  202. 	while(true){
  203. 		if(chain[x] == chain[y]){
  204. 			updateSegTree(pos[y]+flag, pos[x]+1, w);
  205. 			return;
  206. 		}
  207.  
  208. 		ll head = chainHead[chain[x]];
  209. 		updateSegTree(pos[head], pos[x]+1, w);
  210. 		x = p[0][head];
  211. 	}
  212. }
  213.  
  214. ll chainQuery(ll x, ll y, ll flag){
  215. 	ll total = 0;
  216. 	while(true){
  217. 		if(chain[x] == chain[y]){
  218. 			total += querySegTree(pos[y]+flag, pos[x]+1);
  219. 			return total;
  220. 		}
  221.  
  222. 		ll head = chainHead[chain[x]];
  223. 		total += querySegTree(pos[head], pos[x]+1);
  224. 		x = p[0][head];
  225. 	}
  226. }
  227.  
  228. void update(ll u, ll v, ll w){
  229. 	ll lca = LCA(u,v);
  230. 	assert(lca > 0 and lca <= n);
  231. 	chainUpdate(u, lca, w, 0);
  232. 	chainUpdate(v, lca, w, 1);
  233. }
  234.  
  235. ll query(ll u, ll v){
  236. 	ll lca = LCA(u,v);
  237. 	assert(lca > 0 and lca <= n);
  238. 	return chainQuery(u, lca, 0) + chainQuery(v, lca, 1);
  239. }
  240.  
  241. void solve(){
  242. 	sd2(n,q); sd2(A,B);
  243.  
  244. 	if(A == 0)
  245. 		P = (B >= 0)? -INF: INF;
  246. 	else
  247. 		P = (B < 0)? ceil((-1.0*B)/A): (-B)/A;
  248.  
  249. 	for(ll i = 1; i <= n; i++) sd(c[i]);
  250. 	for(int i = 0; i <= 3*n; i++){
  251. 		tree[i] = *(new node);
  252. 	}
  253.  
  254. 	for(int i = 0; i <= n; i++){
  255. 		g[i].clear();
  256. 		sz[i] = 0;
  257. 		lvl[i] = 0;
  258. 		vis[i] = 0;
  259. 		for(int j = 0; j < LOGN; j++) p[j][i] = 0;
  260. 	}
  261.  
  262. 	for(ll i = 1; i < n; i++){
  263. 		ll u, v; sd2(u,v);
  264. 		g[u].pb(v);
  265. 		g[v].pb(u);
  266. 	}
  267.  
  268. 	lvl[1] = 0;
  269. 	for(int j = 0; j < LOGN; j++){
  270. 		p[j][1] = 1;	
  271. 	}
  272.  
  273. 	dfs(1,-1);
  274.  
  275. 	chain_no = 1, indx = -1, chainHead[1] = 1;
  276. 	heavyLightDecomposition(1,-1);
  277.  
  278. 	preprocess();
  279. 	build();
  280.  
  281. 	ll type, u, v, w;
  282. 	while(q--){
  283. 		sd3(type,u,v);
  284. 		if(type == 1){
  285. 			sd(w);
  286. 			update(u,v,w);
  287. 		}
  288. 		else{
  289. 			int res = query(u,v);
  290. 			assert(res >= 0 and res <= n);
  291. 			printf("%lld\n", res);
  292. 		}
  293. 	}
  294. }
  295.  
  296. int main(){
  297. 	ll t; sd(t);
  298. 	while(t--) solve();
  299. 	return 0;
  300. }
Runtime error #stdin #stdout 0.02s 142720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RCaqyR
language:
C++14 (gcc 8.3)
created:
8 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!