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; }