mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #232 (Div. 1) C. On Changing Tree

オイラーツアーツアーその 2 です。

解法

やっぱりオイラーツアーしてセグメント木の問題に落とし込みます。

頂点 v の深さを depth[v] とします。

頂点 v に x を加えた時, v を含む子 u にはどれだけ値が加算されるかというと,
x - k * (depth[u]-depth[v]) = x + k*depth[v] - k*depth[u]

よって, 2 つのセグメント木を用意して, 一つには x + k*depth[v] を区間一様に加えるもの, もうひとつには k を区間一様に加えるものを用意すれば,
seg1[u] - seg2[u] * depth[u]
を求めることで値を求めることが出来ます。

// 遅延評価つきセグメント木
const ll INF = 1ll<<30;
const ll MOD = 1e9+7;
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);
        seg[k] %= MOD;
        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];
            seg[k] %= MOD;
            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) % MOD;
        }
    }
    void update(int a, int b, T x) {
        update(a, b, 0, 0, N, x);
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, N);
    }
};

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

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

int main() {
    int n;
    cin >> n;
    segtree<ll> seg1(2*n), seg2(2*n);
    G.resize(n);
    for (int i = 1; i < n; i++) {
        int p;
        scanf("%d", &p);
        p--;
        G[i].push_back(p);
        G[p].push_back(i);
    }
    createEulerTour(0, -1, 0);
    int m;
    cin >> m;
    while (m--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int v, x, k;
            scanf("%d %d %d", &v, &x, &k);
            v--;
            ll plus = (ll)k * depth[v] + x;
            plus %= MOD;
            seg1.update(BEGIN[v], END[v], plus);
            seg2.update(BEGIN[v], END[v], k);
        } else {
            int v;
            scanf("%d", &v);
            v--;
            ll tmp = seg1.query(BEGIN[v], BEGIN[v]+1);
            tmp -= seg2.query(BEGIN[v], BEGIN[v]+1) * depth[v];
            tmp %= MOD;
            if (tmp < 0) tmp += MOD;
            printf("%I64d\n", tmp);
        }
    }
    return 0;
}