思路：
dfs序+差分数组
分层考虑，通过dfs序来查找修改的区间段，然后用差分数组修改
代码：
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long #define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<int,pii> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e5 + 5; int deep[N], l[N], r[N]; LL ans[N]; vector<int>g[N]; vector<int>d[N]; vector<LL>v[N]; vector<int>t[N]; int x = 0; void dfs(int o, int u, int dd) { deep[u] = dd; d[dd].pb(x); t[dd].pb(u); v[dd].pb(0); l[u] = x; for (int i = 0; i < g[u].size(); i++) { if(g[u][i] != o) { ++x; dfs(u, g[u][i], dd+1); } } r[u] = x; } int main() { int n, m, a, b, c; scanf("%d %d", &n, &m); for (int i = 1; i < n; i++) { scanf("%d %d", &a, &b); g[a].pb(b); g[b].pb(a); } ++x; dfs(1, 1, 0); while(m --) { scanf("%d %d %d", &a, &b, &c); int pos = deep[a] + b; if(pos >= N || d[pos].size() == 0) continue; int st = lower_bound(d[pos].begin(), d[pos].end(), l[a]) - d[pos].begin(); int ed = upper_bound(d[pos].begin(), d[pos].end(), r[a]) - d[pos].begin(); v[pos][st] += c; if(ed < v[pos].size()) v[pos][ed] -= c; } for (int i = 0; i <= n; i++) { if(v[i].size() == 0) break; ans[t[i][0]] = v[i][0]; for (int j = 1; j < v[i].size(); j++) { v[i][j] += v[i][j-1]; ans[t[i][j]] = v[i][j]; } } for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " "[i==n]); return 0; } /* 7 2 1 2 1 3 2 4 2 5 3 6 3 7 2 1 2 3 1 2 */