jiry_2's Blog

首先我不得不吐槽一下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.