CF383C-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 $ a_{i} $ . 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 $ a_{1} $ , $ a_{2} $ , …, $ a_{n} $ $ (1<=a_{i}<=1000) $ . Each of the next $ n–1 $ lines contains two integers $ v_{i} $ and $ u_{i} $ $ (1<=v_{i},u_{i}<=n) $ , meaning that there is an edge between nodes $ v_{i} $ and $ u_{i} $ .
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.
样例:
样例输入1:
1
2
3
4
5
6
7
8
9
10
11
12
| 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
|
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| // Problem: CF383C Propagating tree
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF383C
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
const int maxn = 2e5 + 10;
struct edge
{
int v, nxt;
} e[maxn << 1];
int n, m, head[maxn], tot;
void __ADD(int u, int v)
{
e[++tot] = {v, head[u]};
head[u] = tot;
}
void add(int u, int v)
{
__ADD(u, v), __ADD(v, u);
}
int num, dfn[maxn], st[maxn], ed[maxn], dep[maxn];
void dfs(int u, int fa)
{
dfn[u] = st[u] = ++num;
dep[u] = dep[fa] + 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)
continue;
dfs(v, u);
}
ed[u] = num;
}
int c[maxn], a[maxn];
#define lowbit(x) (x & -x)
void ad(int p, int x)
{
for (; p <= n; p += lowbit(p))
c[p] += x;
}
int q(int p)
{
long long ans = 0;
for (; p; p -= lowbit(p))
ans += c[p];
return ans;
}
int main()
{
yin >> n >> m;
for (int i = 1; i <= n; i++)
yin >> a[i];
for (int i = 1; i < n; i++)
{
int u, v;
yin >> u >> v;
add(u, v);
}
dfs(1, 0);
while (m--)
{
int opt, x, y;
yin >> opt >> x;
if (opt == 1)
{
yin >> y;
// yout << x << " " << st[x] << " " << y << endl;
if (dep[x] & 1)
ad(st[x], y), ad(ed[x] + 1, -y);
else
ad(st[x], -y), ad(ed[x] + 1, y);
}
else
{
long long ans = a[x];
// yout << q(dfn[x]) << endl;
if (dep[x] & 1)
ans += q(dfn[x]);
else
ans -= q(dfn[x]);
yout << ans << endl;
}
}
return 0;
}
|