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
92
93
94
95
96
| #include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x & (-x))
const int MaxN = 1e6 + 10;
struct edge
{
int next, to;
};
struct node
{
int dfn, val, r;
};
node a[MaxN];
edge e[MaxN << 1];
int n, m, r, dfsnum, cnt;
int head[MaxN], vis[MaxN], c[MaxN];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch - '0'), ch = getchar();
return f ? x : (-x);
}
inline void add_edge(int u, int v)
{
++cnt;
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
inline void dfs(int u)
{
vis[u] = true, a[u].dfn = ++dfsnum;
for (int i = head[u]; i; i = e[i].next)
{
int v = e[i].to;
if (!vis[v])
dfs(v);
}
a[u].r = dfsnum;
}
inline void modify(int pos, int x)
{
while (pos <= n)
{
c[pos] += x;
pos += lowbit(pos);
}
}
inline int query(int pos)
{
int ans = 0;
while (pos)
{
ans += c[pos];
pos -= lowbit(pos);
}
return ans;
}
signed main()
{
n = read(), m = read(), r = read();
for (int i = 1; i <= n; i++)
a[i].val = read();
for (int i = 1; i < n; i++)
{
int u = read(), v = read();
add_edge(u, v);
add_edge(v, u);
}
dfs(r);
for (int i = 1; i <= n; i++)
modify(a[i].dfn, a[i].val);
for (int i = 1; i <= m; i++)
{
int op = read();
if (op == 1)
{
int pos = read(), x = read();
modify(a[pos].dfn, x);
}
else
{
int pos = read();
printf("%lld\n", query(a[pos].r) - query(a[pos].dfn - 1));
}
}
return 0;
}
|