树

题目描述

   小L非常喜欢树。最近，他发现了一棵有趣的树。这棵树有n个节点(1到n编号)，节点i有一个初始的权值ai。这棵树的根是节点1。
   这棵树有一个特殊的性质：当你给节点i的权值加 val 的时候，节点i的所有儿子的权值都会加 -val。注意当你给节点i的儿子的权值加 -val 时，节点i的这个儿子的所有儿子的权值都会加 -(-val)，以此类推。样例说明可以很好地帮助你理解这个性质。
   有2种操作：
   操作(a).“1 x val”表示给节点x的权值加val。
   操作(b).“2 x”输出节点x当前的权值。
   为了帮助小L更好地理解这棵树，你必须处理m个操作。

输入

第一行包含2个整数n和m。
第二行包含n个整数a1，a2，…，an（1≤ai≤1000）。
接下来的n-1行，每行两个整数u和v(1≤u接下来的m行，每行包含2种操作的一种。每个操作都保证1≤x≤n，1≤val≤1000。
输出

对于每个操作(b)，输出一个整数，表示节点x当前的权值。
输入样例复制

5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4
输出样例复制

3
3
0
说明

【输入输出样例说明】
初始各个节点的权值依次为[1，2，1，1，2]。 第一个操作给节点2的权值增加3，会给节点2的儿子4、5的权值增加-3。此时各个节点的权值变成[1，5，1，-2，-1]。 第二个操作给节点1的权值增加2，会给节点1的儿子2、3的权值增加-2，然后会给节点2的儿子4、5的权值增加-(-2)。各个节点的权值变成[3，3，-1，0，1]。

【数据说明】
对于50%的数据，1≤n≤2000，1≤m≤2000。
对于100%的数据，1≤n≤100000，1≤m≤100000。
.
.
.
.
.
线段树：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=200001;
int in[maxn],out[maxn],point[maxn],head[maxn],tot,t,vis[maxn],a[maxn],num[maxn],flag[maxn];
struct Edge
{
	int to,next;
}edge[2*maxn];
 
struct data
{
	int l,r,p;
	int laz0,laz1,num;
}node[maxn*4];
 
void add(int x,int y)
{
	edge[tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot++;
}
 
void dfs(int x,int k)
{
	vis[x]=1;
	in[x]=++t;
	num[t]=a[x];
	point[t]=x; 
	flag[x]=k;
	for (int i=head[x];i!=-1;i=edge[i].next)
	{
		int y=edge[i].to;
		if (vis[y]) continue;
		dfs(y,k^1);
	}
	out[x]=t;	
}
 
void build(int x,int y,int cnt)
{
	node[cnt].l=x;
	node[cnt].r=y;
	node[cnt].laz0=node[cnt].laz1=node[cnt].p=0;
	if (x==y)
	{
		node[cnt].p=point[x];
		node[cnt].num=num[x];
		return;
	}
	int mid=(x+y)/2;
	build(x,mid,cnt*2);
	build(mid+1,y,cnt*2+1);
}
 

void down(int cnt)
{
	if (node[cnt].laz0==0&&node[cnt].laz1==0) return;
	int tg0=node[cnt].laz0,tg1=node[cnt].laz1;
	node[2*cnt].laz0+=tg0;
	node[cnt*2].laz1+=tg1;
	node[cnt*2+1].laz0+=tg0;
	node[cnt*2+1].laz1+=tg1;
	if (node[cnt*2].p!=0)
	{
		if (flag[node[cnt*2].p]==0) node[cnt*2].num+=tg0-tg1; else node[cnt*2].num+=tg1-tg0;
	}
	if (node[cnt*2+1].p!=0)
	{
		if(flag[node[cnt*2+1].p]==0) node[cnt*2+1].num+=tg0-tg1; else node[cnt*2+1].num+=tg1-tg0;
	}
	node[cnt].laz0=node[cnt].laz1=0;
}
  
void up(int x,int y,int cnt,int val,int k)
{
	if (x==node[cnt].l&&y==node[cnt].r)
	{
		if (k==0)
		{
			node[cnt].laz0+=val;
			if (node[cnt].p!=0)
			{
				if (flag[node[cnt].p]==0) node[cnt].num+=val; else node[cnt].num-=val;
			}	
		} else
		{
			node[cnt].laz1+=val;
			if (node[cnt].p!=0)
			{
				if (flag[node[cnt].p]==1) node[cnt].num+=val; else node[cnt].num-=val;
			}
		}
		return;
	}
	down(cnt);
	int mid=(node[cnt].l+node[cnt].r)/2;
	if (y<=mid) up(x,y,cnt*2,val,k); else 
	if (x>=mid+1) up(x,y,cnt*2+1,val,k); else
	{
		up(x,mid,cnt*2,val,k);
		up(mid+1,y,cnt*2+1,val,k);
	}
}
 
int find(int x,int y,int cnt)
{	
	if (x==node[cnt].l&&y==node[cnt].r) return node[cnt].num;
	down(cnt);
	int mid=(node[cnt].l+node[cnt].r)/2;
	if (y<=mid) return find(x,y,cnt*2); else 
	if (x>=mid+1) return find(x,y,cnt*2+1);
}
 
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof head);
	memset(vis,0,sizeof vis);
	tot=0;
	t=0;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	build(1,n,1);
	for (int i=1;i<=m;i++)
	{
		int op,x,val;
		scanf("%d%d",&op,&x);
		if(op==1)
		{
			scanf("%d",&val);
			up(in[x],out[x],1,val,flag[x]);
		} else printf("%d
",find(in[x],in[x],1));
	}
	return 0;
}

.
.
.
.
.
树状数组：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,t,tot,l[100001],r[100001],head[100001],flag[100001],f[100001],a[100001];

struct Edge
{
	int to,next;
}edge[2*200001];

void add(int x,int y)
{
	tot++;
	edge[tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
	
	tot++;
	edge[tot].to=x;
	edge[tot].next=head[y];
	head[y]=tot;
}

void dfs(int x,int k)
{
	t++;
	l[x]=t;
	flag[x]=-flag[k];
	for (int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if (y!=k) dfs(y,x);
	}
	r[x]=t;
}

void ins(int x,int y)
{
	for (int i=x;i;i-=i & -i) 
		f[i]+=y;
}
int query(int x)
{
	int sum=0;
	for (int i=x;i<=n;i+=i & -i) 
		sum+=f[i];
	return sum;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	flag[0]=-1;
	dfs(1,0);
	
	for (int i=1;i<=m;i++)
	{
		int rp,x;
		scanf("%d%d",&rp,&x);
		if (rp==1)
		{
			int y;
			scanf("%d",&y);
			ins(r[x],y*flag[x]);
			ins(l[x]-1,-y*flag[x]);
		} else printf("%d
",a[x]+query(l[x])*flag[x]);
	}
	return 0;
}