题目链接：点击传送
2 seconds
256 megabytes
standard input
standard output
Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of n nodes numbered from 1 to n, each node i having an initial value ai. The root of the tree is node 1.
This tree has a special property: when a value val is added to a value of node i, the value -val is added to values of all the children of node i. Note that when you add value -val to a child of node i, you also add -(-val) to all children of the child of node i and so on. Look an example explanation to understand better how it works.
This tree supports two types of queries:
- "1 x val" — val is added to the value of node x;
- "2 x" — print the current value of node x.
In order to help Iahub understand the tree better, you must answer m queries of the preceding type.
The first line contains two integers n and m (1 ≤ n, m ≤ 200000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.
Each of the next m lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.
For each query of type two (print the value of node x) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.
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
The values of the nodes are [1, 2, 1, 1, 2] at the beginning.
Then value 3 is added to node 2. It propagates and value -3 is added to it's sons, node 4 and node 5. Then it cannot propagate any more. So the values of the nodes are [1, 5, 1, - 2, - 1].
Then value 2 is added to node 1. It propagates and value -2 is added to it's sons, node 2 and node 3. From node 2 it propagates again, adding value 2 to it's sons, node 4 and node 5. Node 3 has no sons, so it cannot propagate from there. The values of the nodes are [3, 3, - 1, 0, 1].
You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x) cout<<"bug"<<x<<endl;
const int N=2e5+,M=4e6+,inf=;
const ll INF=1e18+,mod=1e9+;
/// 数组大小
struct is
{
int v,next;
}edge[N<<];
int head[N],edg,a[N];
void init()
{
memset(head,-,sizeof(head));
edg=;
}
void add(int u,int v)
{
edg++;
edge[edg].v=v;
edge[edg].next=head[u];
head[u]=edg;
}
int in[N],out[N],tot,deep[N];
void dfs(int u,int fa,int dep)
{
in[u]=++tot;
deep[u]=dep;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u,dep+);
}
out[u]=tot;
}
/// 线段树
struct SGT
{
int TL[N<<],TR[N<<],ans;
void build(int l,int r,int pos)
{
TL[pos]=TR[pos]=;
if(l==r)return;
int mid=(l+r)>>;
build(l,mid,pos<<);
build(mid+,r,pos<<|);
}
void update(int L,int R,int c,int dep,int l,int r,int pos)
{
if(L<=l&&r<=R)
{
if(dep&)
{
TL[pos]+=c;
TR[pos]-=c;
}
else
{
TL[pos]-=c;
TR[pos]+=c;
}
return;
}
int mid=(l+r)>>;
if(L<=mid)
update(L,R,c,dep,l,mid,pos<<);
if(R>mid)
update(L,R,c,dep,mid+,r,pos<<|);
}
void query(int p,int dep,int l,int r,int pos)
{
if(dep&)
ans+=TL[pos];
else
ans+=TR[pos];
if(l==r)return;
int mid=(l+r)>>;
if(p<=mid)
query(p,dep,l,mid,pos<<);
else
query(p,dep,mid+,r,pos<<|);
}
};
SGT tree;
int main()
{
init();
int n,q;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs(,-,);
tree.build(,n,);
while(q--)
{
int t;
scanf("%d",&t);
if(t==)
{
int x,c;
scanf("%d%d",&x,&c);
tree.update(in[x],out[x],c,deep[x],,n,);
}
else
{
int x;
scanf("%d",&x);
tree.ans=;
tree.query(in[x],deep[x],,n,);
printf("%d\n",tree.ans+a[x]);
}
/*for(int i=1;i<=n;i++)
{
tree.ans=0;
tree.query(in[i],deep[i],1,n,1);
printf("%d ",tree.ans+a[i]);
}
printf("\n");*/
}
return ;
}
2 seconds
256 megabytes
standard input
standard output
Iahub likes trees very much. Recently he discovered an interesting tree named propagating tree. The tree consists of n nodes numbered from 1 to n, each node i having an initial value ai. The root of the tree is node 1.
This tree has a special property: when a value val is added to a value of node i, the value -val is added to values of all the children of node i. Note that when you add value -val to a child of node i, you also add -(-val) to all children of the child of node i and so on. Look an example explanation to understand better how it works.
This tree supports two types of queries:
- "1 x val" — val is added to the value of node x;
- "2 x" — print the current value of node x.
In order to help Iahub understand the tree better, you must answer m queries of the preceding type.
The first line contains two integers n and m (1 ≤ n, m ≤ 200000). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000). Each of the next n–1 lines contains two integers vi and ui (1 ≤ vi, ui ≤ n), meaning that there is an edge between nodes vi and ui.
Each of the next m lines contains a query in the format described above. It is guaranteed that the following constraints hold for all queries: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.
For each query of type two (print the value of node x) you must print the answer to the query on a separate line. The queries must be answered in the order given in the input.
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
The values of the nodes are [1, 2, 1, 1, 2] at the beginning.
Then value 3 is added to node 2. It propagates and value -3 is added to it's sons, node 4 and node 5. Then it cannot propagate any more. So the values of the nodes are [1, 5, 1, - 2, - 1].
Then value 2 is added to node 1. It propagates and value -2 is added to it's sons, node 2 and node 3. From node 2 it propagates again, adding value 2 to it's sons, node 4 and node 5. Node 3 has no sons, so it cannot propagate from there. The values of the nodes are [3, 3, - 1, 0, 1].
You can see all the definitions about the tree at the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)