题目链接
Codeforces Round 225 (Div. 1) C. Propagating tree
思路
每一次操作都是对以 u u u为根的子树的所有节点进行一次操作,因此我们可以用DFS序来将每一棵子树的所有节点限定到一段连续的区间内。
对于子树内每一个节点是进行加或者减操作,跟树的深度有关(也就是深度的奇偶性)。
因此我们可以用一个树状数组来维护区间和,具体操作可见代码。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e4 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m;
int a[N], depth[N], L[N], R[N], cnt;
vector<int> mp[N];
void dfs(int u, int fu, int deep)
{
L[u] = ++cnt;
depth[u] = deep;
for (int j : mp[u])
{
if (j == fu) continue;
dfs(j, u, deep + 1);
}
R[u] = cnt;
}
struct BIT
{
const static int maxnum = 5e5 + 10;
int tree[maxnum];
int lowbit(int x)
{
return (x) & (-x);
}
void add(int idx, int x)
{
for (int pos = idx; pos < maxnum; pos += lowbit(pos))
{
tree[pos] += x;
}
}
int query(int n)
{
int ans = 0;
for (int pos = n; pos; pos -= lowbit(pos))
{
ans += tree[pos];
}
return ans;
}
int query(int a, int b)
{
return query(b) - query(a - 1);
}
void init(int n)
{
for (int i = 0; i <= n + 2; i++)
tree[i] = 0;
}
} tree;
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1, u, v; i < n; i++)
{
cin >> u >> v;
mp[u].push_back(v);
mp[v].push_back(u);
}
dfs(1, -1, 1);
while (m--)
{
int op, x, val;
cin >> op >> x;
if (op == 1)
{
cin >> val;
if (depth[x] & 1) tree.add(L[x], val), tree.add(R[x] + 1, -val);
else tree.add(L[x], -val), tree.add(R[x] + 1, val);
}
else
{
if (depth[x] & 1)
cout << a[x] + tree.query(L[x]) << endl;
else cout << a[x] - tree.query(L[x]) << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int test = 1;
// cin >> test;
for (int i = 1; i <= test; i++)
{
solve();
}
return 0;
}