2017.3.18 2014年初中竞赛试题(南海) 树

2017.3.18 2014年初中竞赛试题(南海) 树

分析：
对于改变，用一个数组记录改变值，求值时，从当前点往根节点走，遇到一个点看该点到求值的点的距离的奇偶，对应加减即可，距离可以每上一层就加1，要先预处理出每个点的父亲即可。

代码：

varn,m,i,x,y,s,j,d:longint;f,t,w,b,e:array[1..100000] of longint;v:array[1..100000] of boolean;a:array[0..200000,1..2] of longint;procedure qsort(l,r:longint);
vari,j,k:longint;
beginif l>=r then exit;i:=l;j:=r;k:=a[(i+j) div 2,1];repeatwhile a[i,1]<k do inc(i);while a[j,1]>k do dec(j);if i<=j thenbegina[0]:=a[i];a[i]:=a[j];a[j]:=a[0];inc(i);dec(j);end;until i>j;qsort(i,r);qsort(l,j);
end;procedure dfs(x:longint);
vari:longint;
beginv[x]:=false;for i:=b[x] to e[x] doif v[a[i,2]] thenbeginf[a[i,2]]:=x;dfs(a[i,2]);end;
end;beginreadln(n,m);for i:=1 to n doread(w[i]);readln;for i:=1 to n-1 dobeginreadln(x,y);a[i*2-1,1]:=x;a[i*2-1,2]:=y;a[i*2,1]:=y;a[i*2,2]:=x;end;qsort(1,n*2-2);a[0,1]:=0;for i:=1 to n*2-2 dobeginif a[i,1]<>a[i-1,1] then b[a[i,1]]:=i;if a[i,1]<>a[i+1,1] then e[a[i,1]]:=i;end;fillchar(v,sizeof(v),true);dfs(1);for i:=1 to m dobeginread(x);if x=1then beginreadln(x,y);t[x]:=t[x]+y;endelse beginreadln(x);s:=w[x];j:=x;d:=0;while j>0 dobegind:=1-d;if d=0then s:=s-t[j]else s:=s+t[j];j:=f[j];end;writeln(s);end;end;
end.