fork download
  1. //NETWRKNB
  2. USES Math;
  3. CONST
  4. tfi = '';
  5. tfo = '';
  6. TYPE
  7. node = record
  8. u,v,k,c,pos,pa: longint;
  9. end;
  10. arr = array[0..100000] of node;
  11. VAR
  12. fi,fo : text;
  13. n,m,cnt,res,jmax,t1,t2 : longint;
  14. ke,next,ts : array[-100000..100000] of longint;
  15. head,free,tin,tout,ans : array[0..100000] of longint;
  16. p,q1,q2,pp : arr;
  17. f : array[0..100000,0..20] of longint;
  18. t,tt : array[0..400000] of longint;
  19.  
  20. Procedure add(i,u,v,c: longint);
  21. Begin
  22. ke[i]:=v;
  23. next[i]:=head[u];
  24. head[u]:=i;
  25. ts[i]:=c;
  26. End;
  27.  
  28. Procedure inp;
  29. Var
  30. i: longint;
  31. Begin
  32. Read(fi,n,m);
  33. For i:=1 to n-1 do
  34. with p[i] do
  35. begin
  36. read(fi,u,v,c);
  37. add(i,u,v,c);
  38. add(-i,v,u,c);
  39. end;
  40. Readln(fi);
  41. jmax:=trunc(ln(n)/ln(2));
  42. End;
  43.  
  44. Procedure dfs(u: longint);
  45. Var
  46. j,v: longint;
  47. Begin
  48. inc(cnt);
  49. tin[u]:=cnt;
  50. j:=1;
  51. While f[u,j-1]<>0 do
  52. begin
  53. f[u,j]:=f[f[u,j-1],j-1];
  54. inc(j);
  55. end;
  56. j:=head[u];
  57. While j<>0 do
  58. begin
  59. v:=ke[j];
  60. If tin[v]=0 then
  61. begin
  62. f[v,0]:=u;
  63. dfs(v);
  64. end;
  65. j:=next[j];
  66. end;
  67. tout[u]:=cnt;
  68. End;
  69.  
  70. Function check(u,v: longint): boolean;
  71. Begin
  72. exit((tin[u]<=tin[v]) and (tout[u]>=tout[v]));
  73. End;
  74.  
  75. Function lca(u,v: longint): longint;
  76. Var
  77. j: longint;
  78. Begin
  79. If check(u,v) then exit(u);
  80. If check(v,u) then exit(v);
  81. For j:=jmax downto 0 do
  82. If (f[u,j]<>0) and not check(f[u,j],v) then u:=f[u,j];
  83. exit(f[u,0]);
  84. End;
  85.  
  86. Procedure swap(var x,y: node);
  87. Var
  88. tg: node;
  89. Begin
  90. tg:=x; x:=y; y:=tg;
  91. End;
  92.  
  93. Procedure qsort(l,r: longint; var a: arr);
  94. Var
  95. i,j,mid,key: longint;
  96. Begin
  97. i:=l;
  98. j:=r;
  99. mid:=l+random(r-l+1);
  100. key:=a[mid].c;
  101. Repeat
  102. While a[i].c<key do inc(i);
  103. While a[j].c>key do dec(j);
  104. If i<=j then
  105. begin
  106. swap(a[i],a[j]);
  107. inc(i);
  108. dec(j);
  109. end;
  110. Until i>j;
  111. If i<r then qsort(i,r,a);
  112. If l<j then qsort(l,j,a);
  113. End;
  114.  
  115. Procedure init;
  116. Var
  117. i,tg: longint;
  118. ch: char;
  119. Begin
  120. dfs(1);
  121. t1:=0; t2:=0;
  122. For i:=1 to m do
  123. begin
  124. read(fi,ch);
  125. If ch='P' then
  126. begin
  127. inc(t1);
  128. with q1[t1] do
  129. begin
  130. read(fi,u,v,c);
  131. pos:=i;
  132. end;
  133. end
  134. else
  135. begin
  136. inc(t2);
  137. with q2[t2] do
  138. begin
  139. read(fi,k,c);
  140. pos:=i;
  141. end;
  142. end;
  143. readln(fi);
  144. end;
  145. For i:=1 to n-1 do pp[i]:=p[i];
  146. qsort(1,n-1,pp);
  147. qsort(1,t1,q1);
  148. qsort(1,t2,q2);
  149. For i:=1 to n-1 do
  150. with pp[i] do
  151. If check(v,u) then
  152. begin
  153. tg:=u; u:=v; v:=tg;
  154. end;
  155. End;
  156.  
  157. Procedure new(i,con1,con2: longint);
  158. Begin
  159. inc(tt[con1],tt[i]);
  160. inc(tt[con2],tt[i]);
  161. inc(t[con1],tt[i]);
  162. inc(t[con2],tt[i]);
  163. tt[i]:=0;
  164. End;
  165. Procedure update(i,l,r,u,v: longint);
  166. Var
  167. mid: longint;
  168. Begin
  169. If (l=u) and (v=r) then
  170. begin
  171. inc(tt[i]);
  172. inc(t[i]);
  173. exit;
  174. end;
  175. If (r<u) or (v<l) then exit;
  176. mid:=(l+r) div 2;
  177. new(i,2*i,2*i+1);
  178. update(2*i,l,mid,u,min(v,mid));
  179. update(2*i+1,mid+1,r,max(mid+1,u),v);
  180. t[i]:=t[2*i]+t[2*i+1];
  181. End;
  182.  
  183. Function get(i,l,r,u,v: longint): longint;
  184. Var
  185. mid: longint;
  186. Begin
  187. If (l=u) and (v=r) then exit(t[i]);
  188. If (r<u) or (v<l) then exit(0);
  189. mid:=(l+r) div 2;
  190. new(i,2*i,2*i+1);
  191. exit(get(2*i,l,mid,u,min(mid,v))+get(2*i+1,mid+1,r,max(mid+1,u),v));
  192. End;
  193.  
  194. Procedure query1;
  195. Var
  196. i,j: longint;
  197. Begin
  198. For i:=1 to t1 do
  199. with q1[i] do pa:=lca(u,v);
  200. j:=1;
  201. For i:=1 to t1 do
  202. with q1[i] do
  203. begin
  204. While (j<=n-1) and (pp[j].c<=c) do
  205. begin
  206. with pp[j] do update(1,1,n,tin[v],tout[v]);
  207. inc(j);
  208. end;
  209. ans[pos]:=get(1,1,n,tin[u],tin[u])+get(1,1,n,tin[v],tin[v])-get(1,1,n,tin[pa],tin[pa])*2;
  210. end;
  211. End;
  212.  
  213. Procedure query2;
  214. Var
  215. i,j,tmp: longint;
  216. Begin
  217. For i:=1 to n*4 do
  218. begin
  219. t[i]:=0; tt[i]:=0;
  220. end;
  221. j:=1;
  222. For i:=1 to t2 do
  223. with q2[i] do
  224. begin
  225. While (j<=n-1) and (pp[j].c<=c) do
  226. begin
  227. with pp[j] do update(1,1,n,tin[u],tin[u]);
  228. inc(j);
  229. end;
  230. with p[k] do
  231. If check(u,v) then tmp:=get(1,1,n,tin[v],tout[v])
  232. else
  233. begin
  234. tmp:=get(1,1,n,1,n)-get(1,1,n,tin[u],tout[u]);
  235. If c<=q2[i].c then dec(res);
  236. end;
  237. ans[pos]:=tmp;
  238. end;
  239. End;
  240.  
  241. Procedure process;
  242. Var
  243. i: longint;
  244. Begin
  245. query1;
  246. query2;
  247. For i:=1 to m do writeln(fo,ans[i]);
  248. End;
  249.  
  250. BEGIN
  251. assign(fi,tfi); reset(fi);
  252. assign(fo,tfo); rewrite(fo);
  253. inp;
  254. init;
  255. process;
  256. close(fi); close(fo);
  257. END.
  258.  
Runtime error #stdin #stdout 0s 25528KB
stdin
Standard input is empty
stdout
An unhandled exception occurred at $080481D3 :
EDivByZero : Division by zero
  $080481D3