E. Propagating tree
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.
Input
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.
Output
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.
Examples
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
output
3 3 0
Note
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)
-------------------------editorial-----------------------------
This is kind of task that needs to be break into smaller subproblems that you can solve independently, then put them together and get solution.
Let’s define level of a node the number of edges in the path from root to the node. Root (node 1) is at level 0, sons of root are at level 1, sons of sons of root are at level 2 and so on.
Now suppose you want to do an operation of type 1 to a node x. What nodes from subtree of x will be added +val (a positive value)? Obviously, x will be first, being located at level L. Sons of x, located at level L + 1 will be added –val. Sons of sons, located at level L + 2, will be added value +val again. So, nodes from subtree of x located at levels L, L + 2, L + 4, ... will be added a +val, and nodes located at levels L + 1, L + 3, L + 5 will be added a –val. Let’s take those values of L modulo 2. All nodes having remainder L modulo 2 will be added a +val, and nodes having reminder (L + 1) modulo 2 will be added –val. In other words, for a fixed x, at a level L, let y a node from subtree of x, at level L2. If L and L2 have same parity, +val will be added to y. Otherwise, -val will be added to y.
From here we have the idea to split nodes of tree in 2 sets – those being located at even level and those being located at odd level. What still makes the problem hard to solve? The fact that we have a tree. If nodes from a subtree would be a contiguous sequence instead of some nodes from a tree, problem would be simpler: the problem would reduce to add / subtract values to all elements of a subarray and query about a current value of an element of array. So, how can we transform tree to an array, such as for a node x, all nodes from subtree of x to be a subarray of array?
The answer is yes. We can do this by properties of DFS search. Before reading on, make sure that you know what is discovery time and finish time in a DFS search. Let’s build 3 arrays now – discover[], representing nodes in order of their discover times (a node is as before in discover as it has a small discover time), begin[] = for a node, in which time it was discovered and end[] = what’s last time of a discovered node before this node finishes. For a subtree of x, all nodes in the subtree are nodes in discover from position begin[x] to end[x].
Example: suppose you have tree 1-5; 1-6; 6-7; 6-4; 4-2; 4-3
Discover is {1, 5, 6, 7, 4, 2, 3}.
begin is {1, 6, 7, 5, 2, 3, 4}.
end is {7, 6, 7, 7, 2, 7, 4}.
What’s subtree of node 6? elements of discover from position begin[6] to end[6]. In this case, from 3 to 7, so elements {6, 7, 4, 2, 3}. You can see it’s correct and take more examples if you want :)
Now, we reduced problem to: you’re given an array A. you can perform 2 operations:
1/ increase all elements from a range [x, y] to a value val (val can be negative, to treat subtractions)
2/ what’s current value of an element from position pos.
Those who solved “Iahub and Xors” from my last round, CF 198, should probably say they saw something similar before. If you didn’t solve problem before, I encourage you to do it after you solve this one, it uses a similar idea to what will follow now. Also, if you don’t know Fenwick trees, please read them before moving on. An alternative would be for this task using segment trees with lazy update, but I see this one more complicated than needed.
I’ll use now a not so common approach when dealing with data structures. Instead of keeping in a node the result, like you usually do, I’ll keep just an auxiliary information. So what algorithm proposed does:
Let A an array, initially with all elements 0.
When you need to update range [x, y] with value val, you simply do A[x] += val and A[y + 1] -= val.
When you need to answer a query about position pos, you output A[1] + A[2] + ... + A[pos].
Implemented brute force, you get O(1) per update and O(N) per query. However, these both are operations supported by a Fenwick tree, so you can get O(logN) per operation.
It may not be very clear why this algorithm works. Let’s take a closer look: an update needs to add value val only to range [x, y]. When you query a position pos, let’s see if algorithm handles it correctly:
1/ pos < x. In this case, result must not be affected by my update. Since pos < x and I only updated 2 values with indices >= x, when doing A[1] + A[2] + ... + A[pos] it won’t matter at all I did that update – at least not for this query.
2/ x <= pos <= y. Here, for a pos, I need to add value val only once. We add it only at A[x] – in this way it will be counted once, and it will be considered for each elements from range [x, y] (since an element at position p from range [x, y] has p >= x, in A[1] + A[2] + ... + A[p] I’ll have to consider A[x]).
3/ pos > y. Here I don’t have to consider the query. But it would be considered when processing A[x]. But if I add to A[y + 1] value –val I’ll just cancel the value previously added.
----------------------------code---------------------------------------
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define nm 200010
int val[nm];
list<int>li[nm];
int ti=0;
int st[nm],en[nm];
vector<int> odd,even,ods,evs;
int seg[2][1200000],lazy[2][1200000];
int lev[nm];
int dfs(int start,int par,int le)
{
list<int>:: iterator it;
lev[start]=le;
if(le%2==1)
{
odd.pb(val[start]);
ods.pb(ti);
}
else
{
even.push_back(val[start]);
evs.pb(ti);
}
st[start]=ti;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(*it!=par)
{
ti++;
// lev[*it]=le+1;
dfs(*it,start,le+1);
}
}
en[start]=ti;
}
update(int idx,int start,int end,int ups,int upe,int type,int value)
{
if(lazy[type][idx])
{
seg[type][idx]+=lazy[type][idx];
if(start!=end)
{
lazy[type][2*idx]+=lazy[type][idx];
lazy[type][2*idx+1]+=lazy[type][idx];
}
lazy[type][idx]=0;
}
if(start>end || start>upe || end<ups) return ;
//cout<<" update "<<idx<<" type "<<type<<" start "<<start<<" end "<<end<<endl;
if(start>=ups && end<=upe)
{
// cout<<" complite inside "<<endl;
// cout<<" initial seg "<<seg[type][idx]<<endl;
seg[type][idx]+=value;
// cout<<" now seg "<<seg[type][idx]<<endl;
if(start!=end)
{
//cout<<" making lazy "<<2*idx<<" "<<2*idx+1<<endl;
lazy[type][2*idx]+=value;
lazy[type][2*idx+1]+=value;
}
return ;
}
update(2*idx,start,(start+end)/2,ups,upe,type,value);
update(2*idx+1,((start+end)/2)+1,end,ups,upe,type,value);
}
int query(int idx,int start,int end,int qs,int qe,int type)
{
// cout<<" query idx "<<idx<<" start "<<start<<" end "<<end<<" type "<<type<<endl;
if(lazy[type][idx])
{
// cout<<" lazy it is "<<endl;
seg[type][idx]+=lazy[type][idx];
if(start!=end)
{
lazy[type][2*idx]+=lazy[type][idx];
lazy[type][2*idx+1]+=lazy[type][idx];
}
lazy[type][idx]=0;
}
if(start>end || start>qe || end<qs) return 0;
else if(start==qs && end==qs)
{
// cout<<" found ret "<<seg[type][idx]<<endl;
return seg[type][idx];
}
int q1=query(2*idx,start,(start+end)/2,qs,qe,type);
int q2=query(2*idx+1,((start+end)/2)+1,end,qs,qe,type);
// cout<<" q1 "<<q1<<" q2 "<<q2<<endl;
return (q1+q2);
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>val[i];
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
li[a].pb(b);
li[b].pb(a);
}
dfs(1,-1,0);
int el=evs.size();
int ol=ods.size();
for(int i=0;i<q;
i++)
{
int type;
scanf("%d",&type);
if(type==1)
{
int idx, value;
scanf("%d %d",&idx,&value);
int start=st[idx];
int end =en[idx];
// cout<<" start end of update is "<<start<<" "<<end<<endl;
// even update
int upv=value;
if(lev[idx]%2==1) upv*=-1;
vector<int>:: iterator it;
it=lower_bound(evs.begin(),evs.end(),start);
if(it!=evs.end() && *it>=start && *it<=end)
{
int lb=it-evs.begin();
it=lower_bound(evs.begin(),evs.end(),end);
if(it==evs.end() || *it>end)
{
it--;
}
int ub=it-evs.begin();
// cout<<" even update "<<lb<<" "<<ub<<" vaue "<<upv<<endl;
update(1,0,el-1,lb,ub,0,upv);
}
// odd update
if(lev[idx]%2==0) value*=-1;
it=lower_bound(ods.begin(),ods.end(),start);
if(it!=ods.end() && *it>=start && *it<=end)
{
int lb=it-ods.begin();
it=lower_bound(ods.begin(),ods.end(),end);
if(it==ods.end() || *it>end)
{
it--;
}
int ub=it-ods.begin();
// cout<<" odd update "<<lb<<" "<<ub<<" value "<<value<<endl;
update(1,0,ol-1,lb,ub,1,value);
}
}
else
{
int idx;
scanf("%d",&idx);
int level=lev[idx];
if(level%2==0)
{
int id=lower_bound(evs.begin(),evs.end(),st[idx])-evs.begin();
// cout<<" query is in even at idx"<<id<<endl;
printf("%d\n",query(1,0,el-1,id,id,0)+val[idx]);
}
else
{
int id=lower_bound(ods.begin(),ods.end(),st[idx])-ods.begin();
// cout<<" query is in odd at idx"<<id<<endl;
printf("%d\n",query(1,0,ol-1,id,id,1)+val[idx]);
}
}
}
}
No comments:
Post a Comment