Apple Tree poj-3321

　　　　题目大意：给你一个根固定的树，每一个点的点权是0或1，查询子树点权和。

　　　　注释：$1\le n \le 10^5$。

　　　　　　想法：刚刚学习dfs序，刷到水题偶哈哈。

　　　　　　　　什么是dfs序？就是在遍历树的时候记录的每个点的出栈入栈序。这样就可以保证每一个节会出现两次且它的子树被其夹在中间。

　　　　　　然后，子树信息就可以通过维护序列的鬼东西维护了qwq。

　　　　　　紧接着，我们用树状数组维护被节点夹着的区间，就是端点节点的子树，用树状数组更新即可。

　　　　最后，附上丑陋的代码... ...

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 100010using namespace std;int tot,cnt;int to[2*maxn],head[maxn],nxt[2*maxn];int d[2*maxn];int p1[maxn],p2[maxn];int tree[4*maxn];inline void add(int x,int y){	to[++tot]=y;	nxt[tot]=head[x];	head[x]=tot;}int lowbit(int x){	return x&(-x);}void dfs(int pos,int fa)//初始构造dfs序{	d[++cnt]=1;	p1[pos]=cnt;	for(int i=head[pos];i;i=nxt[i])	{		if(to[i]==fa) continue;		dfs(to[i],pos);	}	p2[pos]=cnt;}void fix(int x,int ch){	for(int i=x;i<=cnt;i+=lowbit(i))	{		tree[i]+=ch;	}}int query(int x){	int ans=0;	for(int i=x;i;i-=lowbit(i))	{		ans+=tree[i];	}	return ans;}void original(){	cnt=tot=0;	memset(tree,0,sizeof tree);	memset(head,0,sizeof head);}int main(){	int n,m;	while(~scanf("%d",&n))	{		original();		for(int a,b,i=1;i
        
       
      
     

 　　　　小结：dfs序好东西好东西... ...