题意:
n个节点的树,m次询问,每次把v的子树中与v的距离不超过d的节点都加上x。输出最终所有点的值。
n,m <= 3e5,d,x <= 1e9
思路:
每次处理节点u的所有询问,对每个询问,修改差分数组的区间 \([h,h+d]\) 的两个端点。每次把差分前缀和传递给儿子。
每差分完一棵子树都要还原差分数组。
应该算一种幼儿版的树上差分吧。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 5, M = N * 2;
int ha[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[++idx] = b, ne[idx] = ha[a], ha[a] = idx;
}
struct node {int d, x; };
vector<node> q[N];
int n, m;
ll ans[N], dif[N]; //差分数组
void dfs(int u, int fa, int h, ll sum)
{ //h为u的深度, sum为root到u的父亲的前缀和
for(auto &qu : q[u])
{
int l = h, r = h + qu.d;
dif[l] += qu.x;
if(r < n) dif[r+1] -= qu.x; //最大深度n-1
}
sum += dif[h]; ans[u] = sum;
for(int i = ha[u]; i; i = ne[i])
{
int v = e[i]; if(v == fa) continue;
dfs(v, u, h+1, sum);
}
for(auto &qu : q[u]) //还原
{
int l = h, r = h + qu.d;
dif[l] -= qu.x;
if(r < n) dif[r+1] += qu.x;
}
}
signed main()
{
scanf("%d", &n);
for(int i = 1; i < n; i++)
{
int a, b; scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
scanf("%d", &m);
for(int i = 1; i <= m; i++)
{
int v, d, x; scanf("%d%d%d", &v, &d, &x);
q[v].push_back({d, x});
}
dfs(1, -1, 0, 0);
for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}