題目大意：給定一棵以$1$為根的樹，$m$次操作，第$i$次為對以$v_i$為根的深度小于等于$d_i$的子樹的所有節點權值加$x_i$。最后輸出每個節點的值

題解：可以把操作離線，每次開始遍歷到一個節點，把以它為根的操作加上，結束時把這個點的操作刪去。

因為是$dfs$，所以一個點對同一深度的貢獻是一定的，可以用樹狀數組區間加減，求前綴和。但是因為是$dfs$，完全可以把前綴和傳入，就不需要樹狀數組了。

卡點：無

?

C++ Code：

#include <cstdio> #include <vector> #include <cctype> namespace __IO {namespace R {int x, ch;inline int read() {ch = getchar();while (isspace(ch)) ch = getchar();for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);return x;}} } using __IO::R::read;#define maxn 300010int head[maxn], cnt; struct Edge {int to, nxt; } e[maxn << 1]; inline void add(int a, int b) {e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; }int n, m; struct Modify {int d, x;inline Modify() {}inline Modify(int __d, int __x) :d(__d), x(__x){} }; std::vector<Modify> S[maxn];long long pre[maxn], ans[maxn]; void dfs(int u, int fa = 0, int dep = 0, long long sum = 0) {for (std::vector<Modify>::iterator it = S[u].begin(); it != S[u].end(); it++) {pre[dep] += it -> x;if (dep + it -> d + 1 <= n) pre[dep + it -> d + 1] -= it -> x;}sum += pre[dep];ans[u] = sum;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (v != fa) dfs(v, u, dep + 1, sum);}for (std::vector<Modify>::iterator it = S[u].begin(); it != S[u].end(); it++) {pre[dep] -= it -> x;if (dep + it -> d + 1 <= n) pre[dep + it -> d + 1] += it -> x;} } int main() {n = read();for (int i = 1, a, b; i < n; i++) {a = read(), b = read();add(a, b);add(b, a);}m = read();for (int i = 1, v, d, x; i <= m; i++) {v = read(), d = read(), x = read();S[v].push_back(Modify(d, x));}dfs(1);for (int i = 1; i <= n; i++) {printf("%lld", ans[i]);putchar(i == n ? '\n' : ' ');}return 0; }

　　

轉載于:https://www.cnblogs.com/Memory-of-winter/p/9995403.html

總結

以上是生活随笔為你收集整理的[CF1076E]Vasya and a Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。