沈阳网络赛 J题 Ka Chang （树状数组+dfs序+分块思想）

Given a rooted tree ( the root is node 11 ) of NN nodes. Initially, each node has zero point.

Then, you need to handle QQ operations. There're two types:

1\ L\ X1 L X: Increase points by XX of all nodes whose depth equals LL ( the depth of the root is zero ). (x \leq 10^8)(x≤108)

2\ X2 X: Output sum of all points in the subtree whose root is XX.

Input

Just one case.

The first lines contain two integer, N,QN,Q. (N \leq 10^5, Q \leq 10^5)(N≤105,Q≤105).

The next n-1n−1 lines: Each line has two integer aa,bb, means that node aa is the father of node bb. It's guaranteed that the input data forms a rooted tree and node 11 is the root of it.

The next QQ lines are queries.

Output

For each query 22, you should output a number means answer.

样例输入复制

3 3
1 2
2 3
1 1 1
2 1
2 3

样例输出复制

1
0

题目来源

ACM-ICPC 2018 沈阳赛区网络预赛

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
const int maxn = 100100;
const int inf = 0x3f3f3f3f;
const int Big = 1000;
int n, m, head[maxn], cnt, st[maxn], en[maxn], ecnt;
vector<int>deep[maxn];
vector<int>large;
ll c[maxn], extra[maxn];
int read() {
	char ch = ' ';
	int ans = 0;
	while (ch<'0' || ch>'9')
		ch = getchar();
	while (ch <= '9' && ch >= '0') {
		ans = ans * 10 + ch - '0';
		ch = getchar();
	}
	return ans;
}
int lowbit(int x) {
	return x&(-x);
}
ll sum(int x) {
	ll ans = 0;
	while (x) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}
void add_c(int x, int d) {
	while (x <= n) {
		c[x] += d;
		x += lowbit(x);
	}
}
void init() {
	for (int s = 0; s <= n; s++)
		deep[s].clear();
	large.clear();
	cnt = ecnt = 0;
	memset(c, 0, sizeof(c));
	memset(extra, 0, sizeof(extra));
	memset(head, -1, sizeof(head));
}
struct *** {
	int u, v, w, ne;
}ed[maxn];
void add(int u, int v) {
	ed[cnt].u = u; ed[cnt].v = v;
	ed[cnt].ne = head[u]; head[u] = cnt++;
}
void dfs(int x, int dep) {
	st[x] = ++ecnt;
	deep[dep].push_back(st[x]);
	for (int s = head[x]; ~s; s = ed[s].ne) {
		int v = ed[s].v;
		dfs(v, dep + 1);
	}
	en[x] = ecnt;
}
int main() {
	while (~scanf("%d%d", &n, &m)) {
		init();
		for (int s = 1; s < n; s++) {
			int a, b, c;
			a = read(); b = read();
			add(a, b);
		}
		dfs(1, 0);
		for (int s = 1; s <= n; s++)
			if (deep[s].size() >= Big)
				large.push_back(s);
		while (m--) {
			int kind, a, b;
			kind = read();
			if (kind == 1) {
				a = read(); b = read();
				int sz = deep[a].size();
				if (sz < Big)
					for (int s = 0; s < sz; s++) {
						int v = deep[a][s];
						add_c(v, b);
					}
				else
					extra[a] += b;
			}
			else {
				a = read();
				ll fir, sec, ans;
				fir = sum(st[a] - 1); sec = sum(en[a]);
				ans = sec - fir;
				for (int s = 0; s < large.size(); s++) {
					ans += (upper_bound(deep[large[s]].begin(), deep[large[s]].end(), en[a]) -
						lower_bound(deep[large[s]].begin(), deep[large[s]].end(), st[a])) * extra[large[s]];
				}
				printf("%lld\n", ans);
			}
		}
	}
}