首先我不得不吐槽一下BZOJ，出这么一道pascal无解的题目有什么意思呢？我就算优化到极限pascal还是TLE，而C++一个复杂度比我没有花之前的程序居然11S就A了，C++秀优越也用不着这样啊。
先搞个DFS序，这样的话就可以用树状数组来维护了。最终的答案就是add_up(s[k1]) xor add_up(s[k2]) xor w[closefather(k1,k2)]，s是dfs序中最先出现的位置，w是权值。最近公共祖先就用LCA搞掉。就如题目所说，这道题目要用手工栈，不然会在爆栈OJ爆栈。接下来是我无比惨烈的解题截图。（不要怪我没节操的贴了代码）
program p2819;
type
bian=record
next,point:longint;
end;
var
y:array[1..500000,1..4] of longint;
x:array[1..1000010] of longint;
d,w,p,s,e:array[1..500010] of longint;
f:array[1..500010,0..20] of longint;
b:array[1..1000010] of bian;
q,len,i,j,n,k1,k2:longint;
ch:char;
bo:boolean;
function getchar:char;
var
ch:char;
begin
read(ch);
while (ch<>'Q') and (ch<>'C') do
read(ch);
exit(ch);
end;
procedure ade(k1,k2:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
p[k1]:=len;
end;
procedure add(k1,k2:longint);
begin
ade(k1,k2);
ade(k2,k1);
end;
procedure bfs;
var
i,j,head,now:longint;
begin
head:=1; now:=1; y[1,1]:=1; y[1,2]:=p[1]; y[1,3]:=0; y[1,4]:=1;
d[1]:=1; f[1,0]:=0; s[1]:=1;
while now>0 do begin
i:=y[now,2];
if (i<>0) and (b[i].point=y[now,3]) then i:=b[i].next;
if (i=0) then begin
inc(head); e[y[now,1]]:=head;
dec(now);
continue;
end;
inc(now); y[now,1]:=b[i].point; y[now,2]:=p[y[now,1]]; y[now,3]:=y[now-1,1]; y[now,4]:=y[now-1,4]+1;
inc(head); f[y[now,1],0]:=y[now,3]; s[y[now,1]]:=head; d[y[now,1]]:=y[now,4];
y[now-1,2]:=b[i].next;
end;
end;
function lowbit(k:longint):longint;
begin
exit(k and (-k));
end;
procedure add_in(k1,k2:longint);
var
i,j:longint;
begin
i:=k1;
while i<=1000010 do begin
x[i]:=x[i] xor k2;
i:=i+lowbit(i);
end;
end;
function add_up(k:longint):longint;
var
i,num:longint;
begin
i:=k; num:=0;
while i>0 do begin
num:=num xor x[i];
i:=i-lowbit(i);
end;
exit(num);
end;
function go_up(k1,k2:longint):longint;
var
i,j,k:longint;
begin
for k:=0 to 20 do
if 1 shl k>k2 then break;
dec(k); if k<0 then exit(k1);
j:=k1;
for i:=0 to k do
if k2 and (1 shl i)>0 then
j:=f[j,i];
exit(j);
end;
function find(k1,k2:longint):longint;
var
i,j,k:longint;
begin
if d[k1]>d[k2] then begin
i:=k1; k1:=k2; k2:=i;
end;
k2:=go_up(k2,d[k2]-d[k1]);
if k1=k2 then exit(k1);
for k:=1 to 20 do
if 1 shl k>=d[k1] then break;
dec(k);
for i:=k downto 0 do
if f[k1,i]<>f[k2,i] then begin
k1:=f[k1,i]; k2:=f[k2,i];
end;
exit(f[k1,0]);
end;
begin
readln(n);
for i:=1 to n do
read(w[i]);
len:=0;
fillchar(p,sizeof(p),0);
fillchar(b,sizeof(b),0);
for i:=1 to n-1 do begin
readln(k1,k2);
add(k1,k2);
end;
fillchar(d,sizeof(d),0);
len:=0;
bfs;
fillchar(x,sizeof(x),0);
for i:=1 to n do begin
add_in(s[i],w[i]);
add_in(e[i],w[i]);
end;
for i:=1 to 20 do begin
bo:=false;
for j:=1 to n do
if (1 shl i)<d[j] then begin
bo:=true;
f[j,i]:=f[f[j,i-1],i-1];
end;
if bo=false then break;
end;
readln(q);
for i:=1 to q do begin
ch:=getchar;
if ch='Q' then begin
readln(k1,k2);
j:=add_up(s[k1]) xor add_up(s[k2]) xor w[find(k1,k2)];
if j=0 then writeln('No') else writeln('Yes');
end else begin
readln(k1,k2);
add_in(s[k1],w[k1]); add_in(e[k1],w[k1]);
add_in(s[k1],k2); add_in(e[k1],k2);
w[k1]:=k2;
end;
end;
end.
。。。pascal在tyvj上AC了在BZ上WA。要来数据在CENA上AC了再BZ上接着WA。网上抄来PASCAL标程还TM的WA。最后怒了贴个C++结果A了。。。QAQ
！