cf383 C. Propagating tree


题意:

给定一棵树,带点权。两种询问:

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

(0)
上一篇 2022年6月15日
下一篇 2022年6月15日

相关推荐

发表回复

登录后才能评论