fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  4. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  5. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  6. #define rep(i, c)  for(auto &(i) : (c))
  7. #define x     first
  8. #define y     second
  9. #define pb  push_back
  10. #define PB  pop_back()
  11. #define iOS  ios_base::sync_with_stdio(false)
  12. #define sqr(a)  (((a) * (a)))
  13. #define all(a)  a.begin() , a.end()
  14. #define error(x) cerr << #x << " = " << (x) <<endl
  15. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  16. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  17. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  18. #define L(x)  ((x)<<1)
  19. #define R(x)  (((x)<<1)+1)
  20. #define umap  unordered_map
  21. //#define max(x,y)  ((x) > (y) ? (x) : (y))
  22. #define double long double
  23. typedef long long ll;
  24. typedef pair<int,int>pii;
  25. typedef vector<int> vi;
  26. typedef pair<long long,long long> PLL;
  27. const int maxn = 1e5 + 100;
  28. const int maxl = 20;
  29. int sz[maxn], f[maxn], par[maxn][maxl], h[maxn];
  30. vi adj[maxn], adw[maxn];
  31. int chn[maxn];
  32. int w[maxn];
  33. struct node{
  34. 	ll p,s,tot,cnt;
  35. 	node(){
  36. 		cnt = p = s = tot = 0LL;
  37. 	}
  38. 	node(int x){
  39. 		tot = 0LL;
  40. 		p = s = cnt = x;
  41. 	}
  42. 	inline bool ish(){
  43. 		return (cnt == p && p && s);
  44. 	}
  45. 	inline node operator * (node a){
  46. 		node ans;
  47. 		ans.cnt = a.cnt + cnt;
  48. 		bool h = ish(), H = a.ish();
  49. 		ans.tot = a.tot + tot;
  50. 		if(!h && !H){
  51. 			ans.tot += f[s + a.p];
  52. 			ans.p = p;
  53. 			ans.s = a.s;
  54. 		}
  55. 		else if(!h && H){
  56. 			ans.p = p;
  57. 			ans.s = s + a.s;
  58. 		}
  59. 		else if(h && !H){
  60. 			ans.p = p + a.p;
  61. 			ans.s = a.s;
  62. 		}
  63. 		else{
  64. 			ans.p = ans.s = p + a.p;
  65. 		}
  66. 		return ans;
  67. 	}
  68. 	inline ll score(){
  69. 		ll ans = tot + f[p];
  70. 		if(!ish())
  71. 			ans += f[s];
  72. 		return ans;
  73. 	}
  74. 	inline node reverse(){
  75. 		node ans;
  76. 		ans.p = s;
  77. 		ans.s = p;
  78. 		ans.tot = tot;
  79. 		ans.cnt = cnt;
  80. 		return ans;
  81. 	}
  82. };
  83. struct seg{
  84. 	vector<node> s;
  85. 	int sz;
  86. 	seg(){
  87. 	sz = 0;}
  88. 	seg(int n){
  89. 		while(s.size() < 4 * n)
  90. 			s.pb(node());
  91. 		sz = n;
  92. 	}
  93. 	inline void add(int p,int id,int l,int r){
  94. 		if(r - l < 2){
  95. 			s[id] = node(1);
  96. 			return ;
  97. 		}
  98. 		int mid = (l+r)/2;
  99. 		if(p < mid)
  100. 			add(p, L(id), l, mid);
  101. 		else
  102. 			add(p, R(id), mid, r);
  103. 		s[id] = s[L(id)] * s[R(id)];
  104. 	}
  105. 	inline node get(int x,int y,int id,int l,int r){
  106. 		if(x <= l && r <= y)
  107. 			return s[id];
  108. 		int mid = (l+r)/2;
  109. 		if(y <= mid)
  110. 			return get(x, y, L(id), l, mid);
  111. 		else if(mid <= x)
  112. 			return get(x, y, R(id), mid, r);
  113. 		return get(x, y, L(id), l, mid) * get(x, y, R(id), mid, r);
  114. 	}
  115. 	inline void ADD(int p){
  116. 		add(p, 1, 0, sz);
  117. 	}
  118. 	inline node score(int x,int y){
  119. 		return get(x, y, 1, 0, sz);
  120. 	}
  121.  
  122. };
  123. struct query{
  124. 	int ind, mnh, mxh, l;
  125. 	query(){
  126. 	}
  127. 	query(int a,int b,int c,int d){
  128. 		ind = a;
  129. 	 	mnh = b;
  130. 		mxh = c;
  131. 		l = d;
  132. 	}
  133. };
  134. inline bool qcmp (const query &a, const query & q){
  135. 		return a.l < q.l;
  136. 	}
  137. inline bool cmp(const pii &p, const pii &q){
  138. 	if(p.y - q.y)
  139. 		return p.y > q.y;
  140. 	return p.x < q.x;
  141. }
  142. struct chain{
  143. 	int X,x,y;
  144. 	seg s;
  145. 	umap <int, node> MP;
  146. 	chain(){}
  147. 	chain(int a,int b): X(a), y(b){}
  148. 	chain(int a,int b,int c): X(a), x(b), y(c){}
  149. 	vector<pii> vpn;
  150. 	vector<query> QQ;
  151. 	inline void proc(int i){
  152. 		int v = y;
  153. 		while(v != X){
  154. 			if(par[v][0] == X)
  155. 				x = v;
  156. 			vpn.pb({h[v], w[v]});
  157. 			chn[v] = i;
  158. 			v = par[v][0];
  159. 		}
  160. 		sort(all(vpn));
  161. 	}
  162. 	inline void solve(){
  163. 		sort(all(QQ), qcmp);
  164. 		s = seg(vpn.size());
  165. 		vector<pii> vs = vpn;
  166. 		sort(all(vs), cmp);
  167. 		reverse(all(QQ));
  168. 		int po = 0;
  169. 		rep(q, QQ){
  170. 			while(po < vs.size() && vs[po].y >= q.l){
  171. 				int i = lower_bound(all(vpn), pii(vs[po].x, -1)) -  vpn.begin();
  172. 				s.ADD(i);
  173. 				po ++;
  174. 			}
  175. 			int l = lower_bound(all(vpn), pii(q.mnh, -1)) -  vpn.begin();
  176. 			int r = upper_bound(all(vpn), pii(q.mxh, 1e9)) -  vpn.begin();
  177. 			MP[q.ind] = s.score(l, r);
  178. 		}
  179. 	}
  180. };
  181. vector<chain> HLD;
  182. inline int dfs(int v = 0,int p = -1){
  183. 	if(p + 1)
  184. 		h[v] = h[p] + 1;
  185. 	par[v][0] = p;
  186. 	For(i,1,maxl)	if(par[v][i-1] + 1)
  187. 		par[v][i] = par[par[v][i-1]][i-1];
  188. 	sz[v] = 1;
  189. 	For(i,0,adj[v].size()){
  190. 		int u = adj[v][i];
  191. 		if(u - p){
  192. 			w[u] = adw[v][i];
  193. 			sz[v] += dfs(u, v);
  194. 		}
  195. 	}
  196. 	return sz[v];
  197. }
  198. inline void prepHLD(int v = 0,bool h = 0,int f = -1){
  199. 	if(f == -1){
  200. 		if(par[v][0] != -1)
  201. 			f = par[v][0];
  202. 		else
  203. 			f = v;
  204. 	}
  205. 	bool hh = 0, ch = 0, is = 0;
  206. 		rep(u, adj[v]){
  207. 			if(u - par[v][0] && sz[u] * 2 >= sz[v])
  208. 				hh = 1;
  209. 			if(u - par[v][0])
  210. 				ch = 1;
  211. 		}
  212. 	if(par[v][0] != -1){
  213. 		if(h && !hh && !ch)
  214. 			HLD.pb(chain(f,v));
  215. 		if(!h && !ch)
  216. 			HLD.pb(chain(par[v][0],v));
  217. 	}
  218. 	rep(u, adj[v])
  219. 		if(u - par[v][0]){
  220. 			if(sz[u] * 2 < sz[v]){
  221. 				if(!is && !hh)
  222. 					prepHLD(u,1,f);
  223. 				else
  224. 					prepHLD(u);
  225. 			}
  226. 			else
  227. 				prepHLD(u,1,f);
  228. 			is = 1;
  229. 		}
  230. }
  231. inline int lca(int v,int u){
  232. 	if(h[u] > h[v])
  233. 		swap(v, u);
  234. 	rof(i, maxl - 1, -1)
  235. 		if(par[v][i] + 1 && h[par[v][i]] >= h[u])
  236. 			v = par[v][i];
  237. 	if(v == u)	return v;
  238. 	rof(i, maxl - 1, -1)
  239. 		if(par[v][i] - par[u][i])
  240. 			v = par[v][i], u = par[u][i];
  241. 	return par[v][0];
  242. }
  243. inline vi dec(int v,int H){
  244. 	vi ans;
  245. 	while(v + 1 && h[v] > H){
  246. 		ans.pb(chn[v]);
  247. 		v = HLD[chn[v]].X;
  248. 	}
  249. 	return ans;
  250. }
  251. inline vi decompose(int v,int u){
  252. 	int x = lca(v, u);
  253. 	int H = h[x];
  254. 	vi ans = dec(v, H);
  255. 	vi V = dec(u, H);
  256. 	reverse(all(V));
  257. 	rep(w, V)
  258. 		ans.pb(w);
  259. 	return ans;
  260. }
  261. stringstream ss;
  262. inline void prepQ(int i,int v,int w,int l){
  263. 	while(v + 1 && h[v] > h[w]){
  264. 		int j = chn[v];
  265. 		int mnh = h[w] + 1;
  266. 		int mxh = h[v];
  267. 		HLD[j].QQ.pb(query(i, mnh, mxh, l));
  268. 		v = HLD[chn[v]].X;
  269. 	}
  270. }
  271. inline void prepq(int i,int v,int u,int l){
  272. 	ss << v << ' ' << u << ' ' << l << '\n';
  273. 	int w = lca(v, u);
  274. 	prepQ(i, v, w, l);
  275. 	prepQ(i, u, w, l);
  276. }
  277. int IND;
  278. inline ll ANS(){
  279. 	int v,u,l;
  280. 	ss >> v >> u >> l;
  281. 	int w = lca(v, u);
  282. 	vi V = decompose(v, w);
  283. 	vi U = decompose(w, u);
  284. 	node N(0);
  285. 	rep(c, V)
  286. 		N = N * HLD[c].MP[IND].reverse();//, error(HLD[c].MP[IND].reverse().cnt);
  287. 	rep(c, U){
  288. 		N = N * HLD[c].MP[IND];
  289. 	/*	error(HLD[c].MP[IND].cnt);
  290. 		error(HLD[c].MP[IND].p);
  291. 		error(HLD[c].MP[IND].s);
  292. 		error(HLD[c].y);*/
  293.  
  294. 	}
  295. 	IND ++;
  296. 	//Error(N.s, N.p);
  297. 	//error(N.cnt);
  298. 	return N.score();
  299. }
  300. int n,q;
  301. int main(){
  302. 	memset(par, -1, sizeof(par));
  303. 	iOS;
  304. 	cin >> n >> q;
  305. 	For(i,1,n)
  306. 		cin >> f[i];
  307. 	int v,u,w;
  308. 	For(i,1,n){
  309. 		cin >> v >> u >> w;
  310. 		-- v, -- u;
  311. 		adj[v].pb(u);
  312. 		adj[u].pb(v);
  313. 		adw[v].pb(w);
  314. 		adw[u].pb(w);
  315. 	}
  316. 	dfs();
  317. 	prepHLD();
  318. 	For(i,0,HLD.size())
  319. 		HLD[i].proc(i);
  320. 	//error(HLD.size());
  321. 	For(i,0,q){
  322. 		cin >> v >> u >> w;
  323. 		-- v, -- u;
  324. 		prepq(i, v, u, w);
  325. 	}
  326. 	For(i,0,HLD.size())
  327. 		HLD[i].solve();
  328. 	For(i,0,q)
  329. 		cout << ANS() << '\n';
  330.  
  331. }
  332.  
Success #stdin #stdout 0s 15440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N0Vb7e
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!