fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty