[线段树]Vasya and a Tree codeforce1076E

题目链接
题意:给一颗树，有m次操作，每次操作有v, d, x。代表把所有以v为祖先且距离祖先小于d的节点都加上x。
在m次询问后输出n个节点的权值，初始全为零。
思路:
可以发现对编号为1的节点,他最终的权值为所有对v = 1的操作和。对于他的子节点的答案也有贡献。其实祖先节点的操作对子节点没有影响，只是对其相邻的节点有影响。我们可以从1开始dfs，对每次的操作用线段树单点更新深度对应的权值,线段树维护一下所有深度的权值和。对每个节点，就可以算出这个节点的答案 = ${\displaystyle \sum _{i=当前深度}^{n}val\left[i\right]}$i=当前深度∑n​val[i],就可以用线段树搞出来了。dfs出来后还要消除这个节点的影响。。
具体看代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 3e5+5;
const int mod = 1e9+9;
int Case = 1, n;
vector<pair<int,ll> >ve[maxn];
vector<int>G[maxn];
ll res[maxn];
struct node{
	int l, r;
	ll val;
	int mid(){return (l+r)/2;}
}tr[maxn<<2];
void build(int rt, int l, int r) {
	tr[rt].l = l;tr[rt].r = r;tr[rt].val = 0;
	if(l == r) return;
	int mid = tr[rt].mid();
	build(rt<<1, l, mid);
	build(rt<<1|1, mid+1, r);
}
void update(int rt, int pos, ll val) {//单点更新
	if(tr[rt].l == tr[rt].r) {
		tr[rt].val += val;
		return;
	}
	int mid = tr[rt].mid();
	if(pos <= mid) update(rt<<1, pos, val);
	else update(rt<<1|1, pos, val);
	tr[rt].val = tr[rt<<1].val + tr[rt<<1|1].val;
}
ll query(int rt, int l, int r) {//区间询问
	if(tr[rt].l == l && tr[rt].r == r) {
		return tr[rt].val;
	}
	int mid = tr[rt].mid();
	if(r <= mid) return query(rt<<1, l, r);
	else if(l > mid) return query(rt<<1|1, l, r);
	else return query(rt<<1, l, mid) + query(rt<<1|1, mid+1, r);
}
void dfs(int v, int w, int h) {
	for(int i = 0; i < ve[v].size(); i++) {
		int d = ve[v][i].first;
		ll x = ve[v][i].second;
		update(1, min(d+h, n), x);//把对v操作影响的深度都加上去
	}
	res[v] = query(1, h, n);//已经能算出res[v]的结果了
	for(int i = 0; i < G[v].size(); i++) {
		int to = G[v][i];
		if(to != w) dfs(to, v, h+1);
	}
	for(int i = 0; i < ve[v].size(); i++) {
		int d = ve[v][i].first;
		ll x = ve[v][i].second;
		update(1, min(d+h, n), -x);//把v的影响消除
	}
}
void solve() {
    int m;
 	scanf("%d", &n);
 	build(1, 0, n);
 	for(int i = 1; i < n; i++) {
 		int a, b;
 		scanf("%d%d", &a, &b);
 		G[a].push_back(b);
 		G[b].push_back(a);
 	}
	scanf("%d", &m); 	
 	for(int i = 1; i <= m; i++) {
 		ll v, d, x;
 		scanf("%lld%lld%lld", &v, &d, &x);
 		ve[v].push_back(make_pair(d, x));
 	}
 	dfs(1, 0, 0);
 	for(int i = 1; i <= n; i++) printf("%lld ", res[i]);
}

int main() {
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("/Users/hannibal_lecter/Desktop/code/in.txt", "r", stdin);
    //freopen("/Users/hannibal_lecter/Desktop/code/out.txt","w",stdout);
#endif
    while(Case--) {
        solve();
    }
    return 0;
}