题意

给定一棵树，根节点深度为 $0$。有若干询问，每个询问给出一个节点 $v_i$、一个深度 $d_i$ 和一个值 $x_i$，表示对于所有在节点 $v_i$ 的子树中且深度不超过 $depth(v_i) + d_i$ 的节点，其答案需要加上 $x_i$。最终需要输出每个节点的答案。

思路

我们可以使用一种支持区间加、单点查的数据结构（如 Fenwick 树、线段树等）来维护当前深度上的累加值。

从根节点开始进行 DFS，同时维护当前深度 $h$。当进入一个节点 $u$ 时，处理所有以 $u$ 为 $v_i$ 的询问：对于每个这样的询问，在数据结构上的区间 $[h, h + d_i]$ 加上 $x_i$。然后，当前节点 $u$ 的答案就是数据结构中深度 $h$ 位置的值。

当离开节点 $u$ 时，需要撤销之前的所有操作：对于所有以 $u$ 为 $v_i$ 的询问，在区间 $[h, h + d_i]$ 上减去 $x_i$。

算法步骤

1. 读入树的结构，建立邻接表。
2. 读入所有询问，按 $v_i$ 分组存储。
3. 初始化一个支持区间加、单点查的数据结构（如 Fenwick 树），大小为最大深度 $+ 1$。
4. 从根节点（深度 $0$）开始 DFS：
   • 进入节点 $u$ 时，深度为 $h$：
     • 对于每个与 $u$ 相关的询问 $(d_i, x_i)$，在数据结构上对区间 $[h, h + d_i]$ 加上 $x_i$。
     • 查询数据结构中位置 $h$ 的值，作为节点 $u$ 的答案。
   • 递归遍历所有子节点。
   • 离开节点 $u$ 时：
     • 对于每个与 $u$ 相关的询问 $(d_i, x_i)$，在数据结构上对区间 $[h, h + d_i]$ 减去 $x_i$。
5. 输出所有节点的答案。

复杂度分析

• 每个询问在进入和离开节点时各执行一次区间加操作，共 $O(m)$ 次操作。
• 每次区间加和单点查的时间复杂度取决于所使用的数据结构。若使用 Fenwick 树（差分实现），每次操作为 $O(\log N)$，其中 $N$ 为最大深度。
• 总时间复杂度为 $O((n + m) \log N)$。
• 空间复杂度为 $O(n + m)$。

代码说明

• 使用邻接表 adj 存储树。
• 使用 queries[u] 存储所有 $v_i = u$ 的询问，每个询问为一个二元组 $(d_i, x_i)$。
• 使用 Fenwick 树（树状数组）实现区间加、单点查：
  • add(l, r, val)：在位置 $l$ 加 $val$，在位置 $r+1$ 减 $val$。
  • query(pos)：查询前缀和得到位置 $pos$ 的值。
• DFS 函数 dfs(u, h)：
  • 处理进入操作。
  • 递归子节点。
  • 处理离开操作。
• 最终输出数组 ans。

#define B cout << "BreakPoint" << endl;
#define O(x) cout << #x << " " << x << endl;
#define O_(x) cout << #x << " " << x << " ";
#define Msz(x) cout << "Sizeof " << #x << " " << sizeof(x)/1024/1024 << " MB" << endl;
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#define LL long long
const int inf = 1e9 + 9;
const int N = 6e5 + 5;
using namespace std;
inline int read() {
	int s = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			w = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * w;
}
int head[N],to[N],nxt[N],cnt;
void add(int x,int y) {
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}
int n,m;
struct node {
	int d,x;
	inline node() {}
	inline node(int __d, int __x) :d(__d), x(__x){}
};
vector<node> s[N];
LL c[N],ans[N];
void dfs(int u,int fa,int dep,LL sum) {
	for(auto it = s[u].begin();it != s[u].end();it++) {
		c[dep] += it->x;
		if(dep + it->d + 1 <= n) c[dep + it->d + 1] -= it->x;
	}
	sum += c[dep],ans[u] = sum;
	for(int i = head[u];i;i = nxt[i]) {
		int v = to[i];
		if(v != fa) dfs(v,u,dep + 1,sum);
	}
	for(auto it = s[u].begin();it != s[u].end();it++) {
		c[dep] -= it -> x;
		if(dep + it -> d + 1 <= n) c[dep + it -> d + 1] += it -> x;
	}
}
int main() {
	n = read();
	for(int i = 1;i < n;i++) {
		int x = read(),y = read();
		add(x,y),add(y,x);
	}
	m = read();
	for(int i = 1;i <= m;i++) {
		int v = read(),d = read(),x = read();
		s[v].push_back(node(d,x));
	}
	dfs(1,0,0,0);
	for(int i = 1;i <= n;i++) printf("%lld ", ans[i]);
	return 0;
}