CF1076E

如果只是把 $u$ 的 k-son 全部加上 $x$ 就很好做。

大概思路是维护一些vector，第 $i$ 个vector按照dfs序的 $\text{In}$ 值装下所有深度为 $i$ 的节点。然后设 $dep_i$ 为 $i$ 的深度，所有 $u$ 的 k-son 都在第 $dep_u+k$ 个vector中，且 $\text{In}$ 值都在 $[\text{In}_u,\text{Out}_u]$ 中。所以二分查找一下确定 $u$ 的 k-son 在vector中对应的区间，那么把 k-son 加 $x$ 就变成了区间加 $x$，由于没有修改只有最后输出单点查询，所以我是直接用的差分树状数组，但这里是我nt了，直接差分完全可以。

那如果把 0-son,1-son…k-son 全部加呢？只需要再差分一遍（树上差分）就行了。最后问题变为把 $u$ 点权加上 $x$，$u$ 的 k+1-son 减去 $x$。最后统计答案统计树上前缀和就可以了（$u$ 的所有祖先（包括自己）的点权总和）。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define int long long

int c[300005], In[300005], Out[300005], idx[300005], n, cnt;
int s[300005], dep[300005], p[300005];
std::vector<int> G[300005], vec[300005], vec2[300005];
void update(int l, int r, int d) {
	for (int i = l; i <= n; i += (i & ~i + 1)) c[i] += d;
	for (int i = r + 1; i <= n; i += (i & ~i + 1)) c[i] -= d;
}
int query(int x) {
	int sum = 0;
	for (int i = x; i; i -= (i & ~i + 1)) sum += c[i];
	return sum;
}
void dfs(int u, int fa) {
	vec[dep[u] = dep[fa] + 1].push_back(In[u] = ++ cnt);
	vec2[dep[u]].push_back(u);
	for (int v : G[u]) if (v != fa) dfs(v, u);
	Out[u] = cnt;
}
void DFS(int u, int fa) {
	s[u] += query(p[u]);
	for (int v : G[u])
		if (v != fa) s[v] += s[u], DFS(v, u);
}

signed main() {
	scanf("%lld", &n);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%lld%lld", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	dfs(1, -1);
	idx[0] = 1;
	for (int i = 1; vec[i].size(); ++ i) {
		idx[i] = idx[i - 1] + vec[i - 1].size();
		for (int j = 0; j < vec[i].size(); ++ j)
			p[vec2[i][j]] = idx[i] + j;
	}
	int m;
	scanf("%lld", &m);
	for (int i = 1; i <= m; ++ i) {
		int x, d, u, k;
		scanf("%lld%lld%lld", &u, &d, &x);
		s[u] += x, k = dep[u] + d + 1;
		if (n < k || !vec[k].size()) continue;
		int st = std::lower_bound(vec[k].begin(), vec[k].end(), In[u]) - vec[k].begin();
		int ed = std::upper_bound(vec[k].begin(), vec[k].end(), Out[u]) - vec[k].begin() - 1;
		update(idx[k] + st, idx[k] + ed, -x);
	}
	DFS(1, -1);
	for (int i = 1; i <= n; ++ i) printf("%lld ", s[i]);
	return 0;
}