# Codeforces 1076E - Vasya and a Tree - 树状数组

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1076/problem/E

## 实现

https://pasteme.cn/2743

#include <bits/stdc++.h>
const int maxn = int(3e5) + 7;
typedef long long ll;
int n, m, max_dep, dep[maxn];
std::vector<int> edge[maxn];
std::vector<std::pair<int, int>> query[maxn];
struct Bit {
ll data[maxn];
void add(int pos, int val) {
while (pos <= n) data[pos] += val, pos += pos & -pos;
}
ll query(int pos) {
ll ret = 0;
while (pos) ret += data[pos], pos -= pos & -pos;
return ret;
}
} bit;
void dfs(int u, int pre) {
max_dep = std::max(dep[u] = dep[pre] + 1, max_dep);
for (int v : edge[u]) if (v != pre) dfs(v, u);
}
ll ans[maxn];
void solve(int u, int pre) {
for (auto pair : query[u]) {
}
ans[u] = bit.query(dep[u]);
for (int v : edge[u]) if (v != pre) solve(v, u);
for (auto pair : query[u]) {
}
}
int main() {
#ifdef AC
freopen("../in", "r", stdin);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1, u, v; i < n; i++) {
std::cin >> u >> v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1, 1);
std::cin >> m;
for (int i = 1, u, d, x; i <= m; i++) {
std::cin >> u >> d >> x;
query[u].emplace_back(std::min(dep[u] + d, max_dep), x);
}
solve(1, 1);
for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], i == n ? '\n' : ' ');
return 0;
}

Responses