思路:
每个点的最终取值仅受它的祖先(包括自己)的影响,所以可以使用dfs。在dfs的过程中维护全局数组bit及当前深度h,当进入一个深度为h的节点u时,对所有vi = u的query,将区间bit[h, h + di]的值增加xi,那么节点u的最终取值就是bit[h],当离开节点u的时候,不要忘记把对bit数组的的修改操作回溯回去。
实现:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 const int MAXN = 300000; 6 int n, m; 7 int vis[MAXN + 5]; 8 ll ans[MAXN + 5], bit[MAXN + 5]; 9 vector<int> G[MAXN + 5]; 10 vector<pair<int, ll>> upd[MAXN + 5]; 11 12 inline int lowbit(int x) { return x & -x; } 13 14 void add(int x, ll d) 15 { 16 while (x <= MAXN) 17 { 18 bit[x] += d; 19 x += lowbit(x); 20 } 21 } 22 23 ll sum(int x) 24 { 25 ll ans = 0; 26 while (x) 27 { 28 ans += bit[x]; 29 x -= lowbit(x); 30 } 31 return ans; 32 } 33 34 void dfs(int u, int d) 35 { 36 vis[u] = 1; 37 for (int i = 0; i < upd[u].size(); i++) 38 { 39 add(d, upd[u][i].second); 40 add(d + upd[u][i].first + 1, -upd[u][i].second); 41 } 42 ans[u] = sum(d); 43 for (int i = 0; i < G[u].size(); i++) 44 { 45 if (vis[G[u][i]]) continue; 46 dfs(G[u][i], d + 1); 47 } 48 for (int i = 0; i < upd[u].size(); i++) 49 { 50 add(d, -upd[u][i].second); 51 add(d + upd[u][i].first + 1, upd[u][i].second); 52 } 53 } 54 55 int main() 56 { 57 ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 58 int v, d, a, b; ll x; 59 while (cin >> n) 60 { 61 memset(bit, 0, sizeof bit); 62 memset(vis, 0, sizeof vis); 63 for (int i = 1; i <= n; i++) { G[i].clear(); upd[i].clear(); } 64 for (int i = 1; i < n; i++) 65 { 66 cin >> a >> b; 67 G[a].push_back(b); G[b].push_back(a); 68 } 69 cin >> m; 70 for (int i = 1; i <= m; i++) 71 { 72 cin >> v >> d >> x; 73 upd[v].push_back(make_pair(d, x)); 74 } 75 dfs(1, 1); 76 for (int i = 1; i <= n; i++) cout << ans[i] << " "; 77 cout << endl; 78 } 79 return 0; 80 }