Codeforces 396C On Changing Tree(树状数组）

题目链接：Codeforces 396C On Changing Tree

题目大意：给出一棵以1为根的树，形式是从节点2开始给出每个节点的父亲节点；然后是m次操作，操作分为两种，1 v， x， k，表示在以v为根的字数上添加，添加的法则是看这个节点与v节点的距离为i的话，加上x-i*k；2 v查询节点v的值。

解题思路：一开始以为很难，但是突然想到可以先加上在减去就豁然开朗了。首先dfs一遍树，将树映射成树状数组上的位置l[u] ~r[u]表示以u为根的树的范围。然后开两个数组，ad记录添加值，su记录需要减掉得值。关键是在添加的时，添加在ad数组中x+k*d[u]，添加在su数组中k。然后在计算最后答案的时候Sum(ad) - d[u]*Sum(su) （即在最后一步在一起减掉，然后ad数组中每次k*d[u]就保证了不会多减，d为节点的层数）注意最后答案要mod1e9+7，而且注意负数的情况，有时负的很大的话，加一个mod是不够的，可以先取模后再加。

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>

using namespace std;
typedef long long ll;
const int N = 3*1e5+10;
const ll mod = 1e9+7;

int n, k, l[N], r[N], d[N];
ll ad[N], su[N];
vector<int> g[N];

void dfs(int u, int deep) {
	k++;
	l[u] = k;
	d[u] = deep;

	for (int i = 0; i < g[u].size(); i++)
		dfs(g[u][i], deep+1);
	r[u] = k;
}

void init () {
	memset(ad, 0, sizeof(ad));
	memset(su, 0, sizeof(su));

	int a;
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		scanf("%d", &a);
		g[a].push_back(i);
	}

	k = 0;
	dfs(1, 0);
}

void add(int x, ll val, ll* bit) {
	while (x <= k) {
		bit[x] = (bit[x] + val) % mod;
		x += (x&(-x));
	}
}

ll query(int u) {
	int x = l[u];
	ll a = 0, b = 0;
	while (x) {
		a += ad[x];
		b += su[x];
		x -= (x&(-x));
	}
	return ((a - b*d[u])%mod + mod) % mod;
}

int main () {
	init();

	int key, v;
	ll x, y;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &key, &v);
		if (key == 1) {
			cin >> x >> y;
			ll val = (x + d[v] * y) % mod;

			add(l[v], val, ad);
			add(r[v]+1, -val, ad);
			add(l[v], y, su);
			add(r[v]+1, -y, su);
		} else {
			cout << query(v) << endl;
		}
	}
	return 0;
}