[BZOJ1782] [Usaco2010 Feb]slowdown 慢慢游

本文主要是介绍[BZOJ1782] [Usaco2010 Feb]slowdown 慢慢游，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1782

题目大意

给定一棵n个点的树,每次从1出发到达a[i],询问到达a[i]之后,经过了几个之前已经到达的点

题解

简单画下图我们就能发现,每次走完就相当于给a[i]的子树权值(之后到达某个点的答案)+1,为了维护这个,我们用DFS序把子树维护到一条线段上,来回答每次询问
我们需要支持区间修改,单点查询的数据结构,很明显线段树可以,但是我想介绍一下树状数组的写法
树状数组我们知道只能单点修改,区间查询(前缀和),所以这里我们用到差分序列来维护,对于[L,R],单点修改L节点使其加一,R+1节点减一

constmaxn=100010;
vary:array[0..maxn,1..2]of longint;t,x,z:array[0..maxn]of longint;w:array[0..4*maxn,1..2]of longint;i,j,k:longint;n,len,a,b,ans:longint;
procedure init(a,b:longint);
beginw[len,1]:=b;if w[a,2]=0then w[a,2]:=len else w[w[a,1],2]:=len;w[a,1]:=len; inc(len);
end;procedure dfs(a:longint);
var tt:longint;
begininc(len); y[a,1]:=len; z[a]:=len;tt:=w[a,2];while tt<>0 dobegink:=y[w[tt,1],1];if y[w[tt,1],1]=0then dfs(w[tt,1]);tt:=w[tt,2];end;y[a,2]:=len;
end;procedure update(a,b:longint);
beginwhile a<=n dobegininc(t[a],b);inc(a,a and(-a));end;
end;function query(a:longint):longint;
var k:longint;
begink:=0;while a>0 dobegininc(k,t[a]);dec(a,a and(-a));end;exit(k);
end;beginreadln(n); len:=n+1;for i:=1 to n-1 dobeginreadln(a,b);init(a,b); init(b,a);end;for i:=1 to n doreadln(x[i]);len:=0;dfs(1);for i:=1 to n dobeginans:=query(z[x[i]]);update(y[x[i],1],1); update(y[x[i],2]+1,-1);writeln(ans);end;
end.