2017.6.4 入门组 NO.6——树

本文主要是介绍2017.6.4 入门组 NO.6——树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

80%：做不出100%，先来个80分水法首先将x,y之间有边的记录两个，存在a数组里,一个是x,y,另一个是y,x然后将这个a数组排序，将a[i,1]按升序排序。Then 就可以求出每一个点与多少个点有边，求出每一个点的"子点"的区间，用l和r数组存再用dfs求出以1作根，每一个点的father是谁预处理Over如果为1，新建一个数组k来存它们的变化；如果为2，就从这个点往回推，如果为偶数次就+k[j]，如果为奇数次就-k[j],j=father[j]

---

80%代码：

var a:array[0..200000,1..2]of longint;father,l,r,k,d:array[0..100000]of longint;v:array[0..100000]of boolean;n,m,i,j,z,y,x,w:longint;procedure qsort(l,r:longint);
var  i,j,mid:longint;
beginif l>=r then exit;i:=l; j:=r; mid:=a[(l+r) div 2,1];repeatwhile a[i,1]<mid do inc(i);while a[j,1]>mid 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 find_father(x:longint);
var  i:longint;
beginv[x]:=false;for i:=l[x] to r[x] doif v[a[i,2]]=true thenbeginfather[a[i,2]]:=x;find_father(a[i,2]);end;
end;beginreadln(n,m);for i:=1 to n do read(d[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-1)*2);for i:=1 to (n-1)*2 dobeginif a[i,1]<>a[i-1,1] then l[a[i,1]]:=i;if a[i,1]<>a[i+1,1] then r[a[i,1]]:=i;end;fillchar(v,sizeof(v),true);find_father(1);for i:=1 to m dobeginread(x);if x=1 thenbeginreadln(j,y);k[j]:=k[j]+y;end;if x=2 thenbeginreadln(w);j:=w;y:=0;z:=d[w];while j<>0 dobeginy:=1-y;if y=0 then z:=z-k[j] else z:=z+k[j];j:=father[j];end;writeln(z);end;end;
end.

这篇关于2017.6.4 入门组 NO.6——树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---