Codeforces Round #225 (Div. 1) C. Propagating tree

昨日の練習会の D 問題は解法が「オイラーツアーしてセグメント木」という問題だったらしいんですが, そもそもオイラーツアーって名前しか聞いたことがなかったので, ちょっと練習してみました。

問題

Problem - C - Codeforces

解法

「オイラーツアー 木」でググるとわかりやすい資料がたくさん出てきたのでオイラーツアーについてはそれを参考にしてください。

オイラーツアーすると, 木 が 1 次元の配列に落とし込めるので, セグメント木のようなデータ構造が使いやすくなるわけです。

今回の問題を解く上でも, オイラーツアーしてできた配列について, 遅延評価つきセグメント木を使ってクエリを消化していきます。機能としては,
・ある区間 [l, r) に一様に値 x を加える
・ある区間 [l, r) の和を求める
というクエリを頂点数 n に対して で計算できるようにするものです。よくあるやつなので, これも「セグメント木 遅延」とかでググれば情報がたくさん出てきます。

で, 今回の場合はある頂点 v は +val, v の子は -val, v の子の子は +val, ... というように値を足していくことになりますが, これは先ほど作ったオイラツアー配列ではどのように表現できるかというと, v からオイラーツアー配列で偶数個離れた頂点は +val を, 奇数個離れた頂点は -val を加えるようにすれば大丈夫です。

ということで, 2 つのセグメント木 even, odd を作って, 適当に even と odd に val または -val を加えていけば良いです。

// 遅延評価つきセグメント木
const ll INF = 1ll<<30;
template <typename T>
class segtree {
public:
    vector<T> seg;
    vector<T> lazy;
    int N;
    segtree(int V) {
        N = 1;
        while (N < V) N <<= 1;
        seg.resize(2*N-1);
        lazy.resize(2*N-1);
    }
    void lazy_evaluate(int k, int l, int r) {
        seg[k] += lazy[k]*(r-l);
        if (k < N-1) { // if k is not leaf
            lazy[2*k+1] += lazy[k];
            lazy[2*k+2] += lazy[k];
        }
        lazy[k] = 0;
    }
    void update(int a, int b, int k, int l, int r, T x) {
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            lazy[k] += x;
            lazy_evaluate(k, l, r);
        } else {
            lazy_evaluate(k, l, r);
            update(a, b, 2*k+1, l, (l+r)/2, x);
            update(a, b, 2*k+2, (l+r)/2, r, x);
            seg[k] = seg[2*k+1] + seg[2*k+2];
            return;
        }
    }
    T query(int a, int b, int k, int l, int r) {
        lazy_evaluate(k, l, r);
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return seg[k];
        else {
            T lch = query(a, b, 2*k+1, l, (l+r)/2);
            T rch = query(a, b, 2*k+2, (l+r)/2, r);
            return lch + rch;
        }
    }
    void update(int a, int b, T x) {
        update(a, b, 0, 0, N, x);
    }
    int query(int a, int b) {
        return query(a, b, 0, 0, N);
    }
};


// Euler-Tour
const int MAXSIZE = 200020;
int BEGIN[MAXSIZE], END[MAXSIZE];
vector<int> euler_tour;
int K;
vector<vi> G;

void createEulerTour(int v, int p) {
    BEGIN[v] = K++;
    euler_tour.push_back(v);
    for (int el : G[v]) {
        if (el == p) continue;
        createEulerTour(el, v);
        euler_tour.push_back(v);
        K++;
    }
    END[v] = K;
}
int a[MAXSIZE];

int main() {
    int n, m;
    cin >> n >> m;
    G.resize(n);
    segtree<int> even(2*n), odd(2*n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a+i);
    }
    for (int i = 0; i < n-1; i++) {
        int b, c;
        scanf("%d%d", &b, &c);
        b--; c--;
        G[b].push_back(c);
        G[c].push_back(b);
    }
    createEulerTour(0, -1);
    for (int i = 0; i < n; i++) {
        if (BEGIN[i]%2 == 0) {
            even.update(BEGIN[i], BEGIN[i]+1, a[i]);
        } else {
            odd.update(BEGIN[i], BEGIN[i]+1, a[i]);
        }
    }
    while (m--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int x, val;
            scanf("%d%d", &x, &val);
            x--;
            if (BEGIN[x]%2 == 0) {
                even.update(BEGIN[x], END[x], val);
                odd.update(BEGIN[x], END[x], -val);
            } else {
                even.update(BEGIN[x], END[x], -val);
                odd.update(BEGIN[x], END[x], val);
            }
        } else {
            int x;
            scanf("%d", &x);
            x--;
            if (BEGIN[x]%2 == 0) {
                printf("%d\n", even.query(BEGIN[x], BEGIN[x]+1));
            } else {
                printf("%d\n", odd.query(BEGIN[x], BEGIN[x]+1));
            }
        }
    }
    return 0;
}