题意:
给定一棵树,带点权。两种询问:
1 x val:节点 x 加上 val,x 的所有儿子减去 val,x 的所有孙子加上 val,以此类推直到叶子
2 x:输出 x 节点的点权
思路:
维护子树的点权:dfs序把树映射为数组
一层加、一层减:开两个树状数组,/(tr[0]/) 维护在原树中的深度为偶的点,其中深度为奇的无意义;/(tr[1]/) 维护在原树中的深度为奇的点,其中深度为偶的无意义
区间加、单点查询:树状数组维护差分
const signed N = 3 + 2e5;
int n, q, a[N]; vector<int> G[N];
//从st[u]到ed[u]是u的子树
int st[N], ed[N], idx; bool t[N]; //0偶层,1奇层
void dfs(int u, int fa, bool dep) {
st[u] = ++idx; t[u] = dep; //记录节点深度奇偶性
for(int v : G[u]) if(v != fa)
dfs(v, u, !dep);
ed[u] = idx;
}
ll tr[2][N]; //0偶BIT,1奇BIT
void sol() {
cin >> n >> q;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
G[x].pb(y), G[y].pb(x);
}
dfs(1, 0, 1);
for(int i = 1; i <= n; i++) //维护的是差分
add(tr[t[i]], st[i], a[i]), add(tr[t[i]], st[i]+1, -a[i]);
while(q--) {
int op, x, val; cin >> op >> x;
if(op == 1) {
cin >> val;
add(tr[t[x]], st[x], val), add(tr[t[x]], ed[x]+1, -val);
add(tr[!t[x]], st[x], -val), add(tr[!t[x]], ed[x]+1, val);
}
else cout << ask(tr[t[x]], st[x]) << endl;
}
}
原创文章,作者:254126420,如若转载,请注明出处:https://blog.ytso.com/267316.html