1
0

pku3237_zhd.pas 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347
  1. {$M 64000000}
  2. program pku3237;
  3. const maxn=10001;
  4. limit=10000000;
  5. var x,y,v,next:array[1..maxn+maxn]of longint;
  6. ed,whe,list,from,fa,root,fedge,after,fr,RMQ_whe,deep:array[1..maxn]of longint;
  7. sign:array[1..maxn*4]of boolean;
  8. lg,tree,lc,rc,tmin:array[1..maxn*4]of longint;
  9. RMQ:array[0..14,1..maxn*3]of longint;
  10. n,len,num,treelen,quesnum,ques:longint;
  11. procedure add(a,b,c:longint);
  12. begin
  13. inc(len);
  14. x[len]:=a;
  15. y[len]:=b;
  16. v[len]:=c;
  17. next[len]:=from[a];
  18. from[a]:=len;
  19. end;
  20. procedure swap(var x,y:longint);
  21. var t:longint;
  22. begin
  23. t:=x;x:=y;y:=t;
  24. end;
  25. procedure inputint;
  26. var i,a,b,c:longint;
  27. begin
  28. readln(n);
  29. fillchar(from,sizeof(from),0);
  30. len:=0;
  31. for i:=1 to n-1 do
  32. begin
  33. readln(a,b,c);
  34. if a>b then swap(a,b);
  35. add(a,b,c);
  36. add(b,a,c);
  37. end;
  38. end;
  39. function fmax(x,y:longint):longint;
  40. begin
  41. if x>y then fmax:=x else fmax:=y;
  42. end;
  43. function fmin(x,y:longint):longint;
  44. begin
  45. if x<y then fmin:=x else fmin:=y;
  46. end;
  47. procedure maketree;
  48. var i,k,len:longint;
  49. begin
  50. fillchar(fa,sizeof(fa),0);
  51. tree[1]:=1;k:=1;len:=1;fa[1]:=-1;
  52. repeat
  53. i:=from[tree[k]];
  54. while i>0 do
  55. begin
  56. if fa[y[i]]=0 then
  57. begin
  58. inc(len);
  59. tree[len]:=y[i];
  60. fa[y[i]]:=tree[k];
  61. fedge[y[i]]:=i;
  62. end;
  63. i:=next[i];
  64. end;
  65. inc(k);
  66. until k>len;
  67. end;
  68. procedure RMQ_makelist(x,d:longint);
  69. var i:longint;
  70. begin
  71. inc(num);
  72. RMQ[0,num]:=x;
  73. RMQ_whe[x]:=num;
  74. deep[x]:=d;
  75. i:=from[x];
  76. while i>0 do
  77. begin
  78. if fa[y[i]]=x then
  79. begin
  80. RMQ_makelist(y[i],d+1);
  81. inc(num);
  82. RMQ[0,num]:=x;
  83. end;
  84. i:=next[i];
  85. end;
  86. end;
  87. procedure make_RMQ;
  88. var len,k,i:longint;
  89. begin
  90. num:=0;
  91. RMQ_makelist(1,1);
  92. len:=2;k:=1;
  93. while len<=num do
  94. begin
  95. for i:=1 to num-len+1 do
  96. if deep[RMQ[k-1,i]]<deep[RMQ[k-1,i+len shr 1]] then
  97. RMQ[k,i]:=RMQ[k-1,i]
  98. else RMQ[k,i]:=RMQ[k-1,i+len shr 1];
  99. inc(k);
  100. len:=len shl 1;
  101. end;
  102. lg[1]:=0;k:=0;
  103. for i:=2 to num do
  104. begin
  105. if 1 shl (k+1)<=i then inc(k);
  106. lg[i]:=k;
  107. end;
  108. end;
  109. function getLCA(a,b:longint):longint;
  110. var k:longint;
  111. begin
  112. a:=RMQ_whe[a];
  113. b:=RMQ_whe[b];
  114. if a>b then swap(a,b);
  115. k:=lg[b-a+1];
  116. if deep[RMQ[k,a]]<deep[RMQ[k,b-1 shl k+1]] then getLCA:=RMQ[k,a]
  117. else getLCA:=RMQ[k,b-1 shl k+1];
  118. end;
  119. procedure buildtree(len,l,r:longint);
  120. begin
  121. if l=r then
  122. begin
  123. tree[len]:=v[fedge[list[l+1]]];
  124. tmin[len]:=v[fedge[list[l+1]]];
  125. exit;
  126. end;
  127. inc(treelen);
  128. lc[len]:=treelen;
  129. buildtree(treelen,l,(l+r)shr 1);
  130. inc(treelen);
  131. rc[len]:=treelen;
  132. buildtree(treelen,(l+r)shr 1+1,r);
  133. tree[len]:=fmax(tree[lc[len]],tree[rc[len]]);
  134. tmin[len]:=fmin(tmin[lc[len]],tmin[rc[len]]);
  135. end;
  136. procedure makelist(x:longint);
  137. var sta,i,j:longint;
  138. begin
  139. if after[x]=0 then exit;
  140. sta:=x;
  141. repeat
  142. inc(num);
  143. fr[x]:=sta;
  144. whe[x]:=num;
  145. list[num]:=x;
  146. x:=after[x];
  147. until x=0;
  148. ed[sta]:=num;
  149. inc(treelen);
  150. root[sta]:=treelen;
  151. buildtree(treelen,whe[sta],ed[sta]-1);
  152. for j:=whe[sta] to ed[sta] do
  153. begin
  154. x:=list[j];
  155. i:=from[x];
  156. while i>0 do
  157. begin
  158. if (y[i]<>after[x])and(y[i]<>fa[x]) then
  159. makelist(y[i]);
  160. i:=next[i];
  161. end;
  162. end;
  163. end;
  164. procedure makeway;
  165. var i:longint;
  166. begin
  167. fillchar(list,sizeof(list),0);
  168. fillchar(after,sizeof(after),0);
  169. fillchar(fr,sizeof(fr),0);
  170. for i:=n downto 2 do
  171. begin
  172. inc(list[tree[i]]);
  173. if list[tree[i]]>list[fa[tree[i]]] then
  174. begin
  175. list[fa[tree[i]]]:=list[tree[i]];
  176. after[fa[tree[i]]]:=tree[i];
  177. end;
  178. end;
  179. num:=0;
  180. makelist(1);
  181. end;
  182. procedure maintain(i:longint);
  183. var t:longint;
  184. begin
  185. if sign[i] then
  186. begin
  187. sign[i]:=false;
  188. sign[lc[i]]:=not sign[lc[i]];
  189. sign[rc[i]]:=not sign[rc[i]];
  190. t:=tree[lc[i]];
  191. tree[lc[i]]:=-tmin[lc[i]];
  192. tmin[lc[i]]:=-t;
  193. t:=tree[rc[i]];
  194. tree[rc[i]]:=-tmin[rc[i]];
  195. tmin[rc[i]]:=-t;
  196. tree[i]:=fmax(tree[lc[i]],tree[rc[i]]);
  197. tmin[i]:=fmin(tmin[lc[i]],tmin[rc[i]]);
  198. end;
  199. end;
  200. function check_max(a,b,l,r,i:longint):longint;
  201. var mid:longint;
  202. begin
  203. if (l=a)and(r=b) then check_max:=tree[i]
  204. else
  205. begin
  206. maintain(i);
  207. mid:=(l+r)shr 1;
  208. if b<=mid then check_max:=check_max(a,b,l,mid,lc[i])
  209. else if a>mid then check_max:=check_max(a,b,mid+1,r,rc[i])
  210. else check_max:=fmax(check_max(a,mid,l,mid,lc[i]),
  211. check_max(mid+1,b,mid+1,r,rc[i]));
  212. end;
  213. end;
  214. function work_query(a,b:longint):longint;
  215. var t1,t2:longint;
  216. begin
  217. if a=b then begin work_query:=-limit;exit end;
  218. if (fr[a]=0)or(fr[a]=a) then
  219. begin
  220. t1:=v[fedge[a]];
  221. t2:=work_query(fa[a],b);
  222. work_query:=fmax(t1,t2);
  223. end
  224. else begin
  225. if fr[a]<>fr[b] then
  226. begin
  227. t1:=check_max(whe[fr[a]],whe[a]-1,whe[fr[a]],ed[fr[a]]-1,root[fr[a]]);
  228. t2:=work_query(fr[a],b);
  229. work_query:=fmax(t1,t2);
  230. end
  231. else
  232. work_query:=check_max(whe[b],whe[a]-1,whe[fr[a]],ed[fr[a]]-1,root[fr[a]]);
  233. end;
  234. end;
  235. procedure tree_change(x,l,r,i,c:longint);
  236. var mid:longint;
  237. begin
  238. if l=r then begin tree[i]:=c;tmin[i]:=c;sign[i]:=false end
  239. else begin
  240. maintain(i);
  241. mid:=(l+r)shr 1;
  242. if x<=mid then tree_change(x,l,mid,lc[i],c)
  243. else tree_change(x,mid+1,r,rc[i],c);
  244. tree[i]:=fmax(tree[lc[i]],tree[rc[i]]);
  245. tmin[i]:=fmin(tmin[lc[i]],tmin[rc[i]]);
  246. end;
  247. end;
  248. procedure work_change(p,c:longint);
  249. var a,b:longint;
  250. begin
  251. v[p]:=c;v[p+1]:=c;
  252. if fa[x[p]]=y[p] then begin a:=x[p];b:=y[p] end
  253. else begin a:=y[p];b:=x[p] end;
  254. if (fr[a]<>0)and(fr[a]<>a) then
  255. tree_change(whe[b],whe[fr[a]],ed[fr[a]]-1,root[fr[a]],c);
  256. end;
  257. procedure tree_negate(a,b,l,r,i:longint);
  258. var t,mid:longint;
  259. begin
  260. if (a=l)and(b=r) then
  261. begin
  262. sign[i]:=not sign[i];
  263. t:=tree[i];
  264. tree[i]:=-tmin[i];
  265. tmin[i]:=-t;
  266. end
  267. else
  268. begin
  269. maintain(i);
  270. mid:=(l+r)shr 1;
  271. if b<=mid then tree_negate(a,b,l,mid,lc[i])
  272. else if a>mid then tree_negate(a,b,mid+1,r,rc[i])
  273. else begin
  274. tree_negate(a,mid,l,mid,lc[i]);
  275. tree_negate(mid+1,b,mid+1,r,rc[i]);
  276. end;
  277. tree[i]:=fmax(tree[lc[i]],tree[rc[i]]);
  278. tmin[i]:=fmin(tmin[lc[i]],tmin[rc[i]]);
  279. end;
  280. end;
  281. procedure work_negate(a,b:longint);
  282. begin
  283. if a=b then exit;
  284. if (fr[a]=0)or(fr[a]=a) then
  285. begin
  286. v[fedge[a]]:=-v[fedge[a]];
  287. if x[fedge[a]]<y[fedge[a]] then v[fedge[a]+1]:=-v[fedge[a]+1]
  288. else v[fedge[a]-1]:=-v[fedge[a]-1];
  289. work_negate(fa[a],b);
  290. end
  291. else
  292. if fr[a]<>fr[b] then
  293. begin
  294. tree_negate(whe[fr[a]],whe[a]-1,whe[fr[a]],ed[fr[a]]-1,root[fr[a]]);
  295. work_negate(fr[a],b);
  296. end
  297. else
  298. tree_negate(whe[b],whe[a]-1,whe[fr[a]],ed[fr[a]]-1,root[fr[a]]);
  299. end;
  300. procedure work;
  301. var ch:char;
  302. a,b,ro,t1,t2:longint;
  303. begin
  304. fillchar(sign,sizeof(sign),0);
  305. maketree;
  306. treelen:=0;
  307. makeway;
  308. make_RMQ;
  309. read(ch);
  310. while ch<>'D' do
  311. begin
  312. case ch of
  313. 'Q':begin
  314. read(ch,ch,ch,ch);
  315. readln(a,b);
  316. ro:=getLCA(a,b);
  317. t1:=work_query(a,ro);
  318. t2:=work_query(b,ro);
  319. writeln(fmax(t1,t2));
  320. end;
  321. 'C':begin
  322. read(ch,ch,ch,ch,ch);
  323. readln(a,b);
  324. work_change(a shl 1-1,b);
  325. end;
  326. 'N':begin
  327. read(ch,ch,ch,ch,ch);
  328. readln(a,b);
  329. ro:=getLCA(a,b);
  330. work_negate(a,ro);
  331. work_negate(b,ro);
  332. end;
  333. end;
  334. read(ch);
  335. end;
  336. readln;
  337. end;
  338. begin
  339. readln(quesnum);
  340. for ques:=1 to quesnum do
  341. begin
  342. readln;
  343. inputint;
  344. work;
  345. end;
  346. end.