Codeforces 396(#232 Div1) C. On Changing Tree

問題

n頂点からなる木が与えられる。頂点には数字が記憶されていて、最初は全て0.
これにq個のクエリが来るので処理せよ。

• 1 v x k

頂点vにxを足す。
vの子孫全てにvからの距離がdならばx - k*dを足す。

• 0 v

頂点vの数字をmod 10^9 + 7で答える。

制約条件

n≦3*10^5
x, k＜mod

方針

オイラーツアーして一次元にして考える。

値はなんかdepthの一次式になってるので、一次の係数とゼロ次の係数のbinary indexed treeを持っておく、よくある手法で出来る。

頂点vの値を考えるとき、自分かそれ以上根に近いの頂点に保存された一次の係数の和をx1,
0次の係数の和をx0とすれば、valueは
value = depth * x1 + x0という式で表せる。

オイラーツアーして、頂点vの出てくる位置をp1, p2とすれば、
p1にhogeを足して、p2に-hogeを足せば、vから根以外の枝の頂点から和を取ると打ち消しあって消えるので、vの子孫だけにhogeを足すことができる。

で、hogeをいくつにすればいいかと言うと、
value += x - k * (d - depth[v])という式になるから、
value += -kd + x + k*depth[v]となって、
x1に-k, x0にx + k*depth[v]を足せばいい、となる。

超典型問のはずなのに、グラフの平方分割とかそういうことを考えてて、
ライブラリないムリゲーとか思ってあきらめてた。頭悪すぎだった。

ソースコード

const int MX = 600010;
const int mod = (int)1e9 + 7;

int bit1[MX], bit0[MX];
void add(int *bit, int i, int x){
	for(; i < MX; i += i & -i) (bit[i] += x) %= mod;
}
int sum(int *bit, int i){
	ll res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res % mod;
}

int n;
vi e[MX];

int pos[MX][2], depth[MX], sz; //pos in the eular tour

void dfs(int c, int d = 0){
	depth[c] = d;
	pos[c][0] = sz++;
	rep(i, e[c].size()) dfs(e[c][i], d + 1);
	pos[c][1] = sz++;
}

int main(){
	cin >> n;
	rep(i, n - 1){
		int p; cin >> p;
		e[p - 1].pb(i + 1);
	}
	sz = 1;
	dfs(0);
	
	int q; cin >> q;
	while(q--){
		int t, v, x, k; cin >> t >> v;
		v--;
		
		if(t == 1){
			cin >> x >> k;
			int p1 = pos[v][0], p2 = pos[v][1], d = depth[v];
			add(bit1, p1, mod - k); add(bit1, p2, k);
			add(bit0, p1, (x + (ll)d * k) % mod); add(bit0, p2, mod - (x + (ll)d * k) % mod);
		}
		else{
			int p = pos[v][0];
			cout << (sum(bit1, p) * (ll)depth[v] + sum(bit0, p)) % mod << endl;
		}
	}
	return 0;
}