【codeforces 384 E】Propagating tree中国語題意&題解&コード(c++)
11482 ワード
E. Propagating tree
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard 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.
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.
Sample test(s)
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].
タイトル:
n個の点を与え,m個の問合せの無方向ツリー(1はルート)
次のn個の数は各点の重み値を表す
次のn-1行はツリーを与えます
操作1:xポイント重み+v,xのサブノードでxのツリー内のレイヤ数のパリティと同じノード重み+v,パリティの異なるノード重み-v.
操作2:xポイントの重み値を尋ねる
問題:
xおよびxのサブノードに値を付けるには、DFSシーケンスでセグメントツリーを構築し、区間修正を行うことが明らかになりますが、難点は、異なるパリティのノードに異なる値を加える方法です.私たちは2本の異なるセグメントツリーを構築することができます.1本は奇数層の点を保存し、もう1本は偶数層の点を保存することができます.(奇数線分ツリーであれば、各ノードが表す区間の奇数層の点数を統計し、これにより、伝達されるたびにこのノードに加算される値はtree[id].shu*v、偶数の線分ツリーに類似する)、追加するたびにその中の1本に与える(xパリティと同じ株)vを加え、別の株に-vを加え、最後にある点をクエリーする場合は、2本のセグメントツリーで検索し、得られた値を加算すればよい.
注:1本の線分樹で書こうと思ったのですが、線分樹の節点間が伝わるのが乱れているような気がしますので、1本の線分樹の書き方は大神さんが自分で試してみてください.コードを共有できるようにしたほうがいいです(-.-)!
コード:
time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard 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.
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.
Sample test(s)
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].
タイトル:
n個の点を与え,m個の問合せの無方向ツリー(1はルート)
次のn個の数は各点の重み値を表す
次のn-1行はツリーを与えます
操作1:xポイント重み+v,xのサブノードでxのツリー内のレイヤ数のパリティと同じノード重み+v,パリティの異なるノード重み-v.
操作2:xポイントの重み値を尋ねる
問題:
xおよびxのサブノードに値を付けるには、DFSシーケンスでセグメントツリーを構築し、区間修正を行うことが明らかになりますが、難点は、異なるパリティのノードに異なる値を加える方法です.私たちは2本の異なるセグメントツリーを構築することができます.1本は奇数層の点を保存し、もう1本は偶数層の点を保存することができます.(奇数線分ツリーであれば、各ノードが表す区間の奇数層の点数を統計し、これにより、伝達されるたびにこのノードに加算される値はtree[id].shu*v、偶数の線分ツリーに類似する)、追加するたびにその中の1本に与える(xパリティと同じ株)vを加え、別の株に-vを加え、最後にある点をクエリーする場合は、2本のセグメントツリーで検索し、得られた値を加算すればよい.
注:1本の線分樹で書こうと思ったのですが、線分樹の節点間が伝わるのが乱れているような気がしますので、1本の線分樹の書き方は大神さんが自分で試してみてください.コードを共有できるようにしたほうがいいです(-.-)!
コード:
#includeint v=lin[x][i];
if (v!=f)
{
dfs(v,x,d+1);
size[x]+=size[v];
}
}
return ;
// dfs
}
void push_up(int id,int o)
{
tree[o][id].val=tree[o][lson].val+tree[o][rson].val;
tree[o][id].shu=tree[o][lson].shu+tree[o][rson].shu;
return ;
}
void push_down(int id,int l,int r,int o)
{
int mid=(l+r)/2;
tree[o][lson].val+=tree[o][id].lazy*tree[o][lson].shu;
tree[o][rson].val+=tree[o][id].lazy*tree[o][rson].shu;
tree[o][lson].lazy+=tree[o][id].lazy;
tree[o][rson].lazy+=tree[o][id].lazy;
tree[o][id].lazy=0;
return ;
}
void build_tree(int id,int l,int r,int o)
{
tree[o][id].lazy=0;
if (l==r)
{
if (dp[mp[l]]%2==o)
{
tree[o][id].shu=1;
tree[o][id].val=a[mp[l]];
//
}
return ;
}
int mid=(l+r)/2;
build_tree(lson,l,mid,o);
build_tree(rson,mid+1,r,o);
push_up(id,o);
return ;
}
void add(int id,int l,int r,int L,int R,int v,int o)
{
if (l>=L&&r<=R)
{
tree[o][id].val+=tree[o][id].shu*v;
tree[o][id].lazy+=v;
return ;
}
push_down(id,l,r,o);
int mid=(l+r)/2;
if (mid>=L)
add(lson,l,mid,L,R,v,o);
if (mid+1<=R)
add(rson,mid+1,r,L,R,v,o);
push_up(id,o);
return ;
}
int query(int id,int l,int r,int o,int x)
{
if (l==r&&r==x)
return tree[o][id].val;
push_down(id,l,r,o);
int mid=(l+r)/2;
if (mid>=x)
return query(lson,l,mid,o,x);
if (mid+1<=x)
return query(rson,mid+1,r,o,x);
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;iint u,v;
scanf("%d%d",&u,&v);
lin[u].push_back(v);
lin[v].push_back(u);
}
dfs(1,1,1);
build_tree(1,1,n,1);
build_tree(1,1,n,0);
for (int i=1;i<=m;i++)
{
int q,aa,bb;
scanf("%d",&q);
if (q==2)
{
scanf("%d",&aa);
int ans=query(1,1,n,1,w[aa])+query(1,1,n,0,w[aa]);
printf("%d
",ans);
}
else
{
scanf("%d%d",&aa,&bb);
add(1,1,n,w[aa],w[aa]+size[aa]-1,bb,dp[aa]%2);
add(1,1,n,w[aa],w[aa]+size[aa]-1,-bb,(dp[aa]+1)%2);
}
}
}