CF383C Propagating tree

传送门

Solution

一棵子树中的所有点的 dfs 序必定连续，因此先 dfs 求出每个点的 dfs 序和深度，以及该子树的点的 dfs 序的左右边界。

然后就可以以 dfs 序为序列，建立线段树维护。当 $T_i$ 是线段树的非叶节点时，其充当 lazy tag 的作用。从 $T_i$ pushdown 到叶节点时，根据叶节点对应树中节点的深度奇偶性，决定将 $T_i$ 加或减到叶节点上。若 pushdown 到非叶节点，则该子节点直接加上 $T_i$ 并将 $T_i$ 清零。

根据上述规则，执行操作 1 时，根据子树根节点的深度奇偶性决定将 $val$ 还是 $-val$ 加到线段树对应区间上。

Code

#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;

const ll N = 2e5 + 10;

ll n, m, L[N], dfn_cnt, a[N], R[N], siz[N], dep[N], mp[N];
struct Node {
    ll l, r, sum, siz;
} T[N << 2];
vector<ll> g[N];

void dfs(ll u, ll pre)
{
    dep[u] = dep[pre] + 1;
    L[u] = ++dfn_cnt;
    siz[u] = 1;
    for (ll v : g[u]) {
        if (v == pre) continue;
        dfs(v, u);
        siz[u] += siz[v];
    }
    R[u] = dfn_cnt;
}

void build(ll k, ll l, ll r)
{
    T[k].l = l; T[k].r = r; T[k].siz = r - l + 1;
    if (l == r) {
        T[k].sum = a[mp[l]];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void push_down(ll k) 
{
    if (T[ls].siz == 1) {
        if (dep[mp[T[ls].l]] & 1)
            T[ls].sum += T[k].sum;
        else
            T[ls].sum -= T[k].sum;
    } else
        T[ls].sum += T[k].sum;
    if (T[rs].siz == 1) {
        if (dep[mp[T[rs].l]] & 1)
            T[rs].sum += T[k].sum;
        else
            T[rs].sum -= T[k].sum;
    } else
        T[rs].sum += T[k].sum;
    T[k].sum = 0;
}

void modify(ll k, ll x, ll y, ll z)
{
    if (x <= T[k].l && T[k].r <= y) {
        if (T[k].siz > 1)
            T[k].sum += z;
        else {
            if (dep[mp[T[k].l]] & 1)
                T[k].sum += z;
            else
                T[k].sum -= z;
        }
        return;
    }
    ll mid = (T[k].l + T[k].r) >> 1;
    push_down(k);
    if (x <= mid) modify(ls, x, y, z);
    if (mid < y) modify(rs, x, y, z);
}

ll query(ll k, ll x)
{
    if (T[k].l == T[k].r && T[k].l == x)
        return T[k].sum;
    push_down(k);
    ll mid = (T[k].l + T[k].r) >> 1;
    if (x <= mid) return query(ls, x);
    else return query(rs, x);
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i < n; i++) {
        ll u, v;
        scanf("%lld%lld", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        mp[L[i]] = i;
    build(1, 1, n);
    while (m--) {
        ll opt, x, y;
        scanf("%lld%lld", &opt, &x);
        if (opt == 1) {
            scanf("%lld", &y);
            if (dep[x] & 1)
                modify(1, L[x], R[x], y);
            else
                modify(1, L[x], R[x], -y);
        } else 
            printf("%lld\n", query(1, L[x]));
    }
    return 0;
}