Codeforces 1076E——回溯

Codeforces 1076E——回溯

题意：给出一棵以1为根的有根树，边权全部为1，点权初始全部为0，给出m个查询，每个查询给出三个变量v d x，表示将v节点的子节点（包括自己）中与v之间的距离<=d的节点的点权增加x，问最后每个节点的点权是多少

1<=n<=3e5, 1<=m<=3e5,1<=v<=n, 1<=d, x<=1e9

思路：开一棵线段树表示某个深度上增加的值，这样在dfs到一个节点时，首先将它身上的查询更新一下，回溯时再将之前的更新取消就可以了

#include using namespace std;const int maxn = 3e5 + 10;typedef long long ll;typedef pair P;int n, m;int tot, head[maxn];struct Edge { int to, next; }edges[maxn<<1];vector

vec[maxn];ll a[maxn<<2], lazy[maxn<<2], res[maxn];void addedge(int u, int v) { edges[tot].to = v; edges[tot].next = head[u]; head[u] = tot++;}void pushup(int root) { a[root] = a[root<<1] + a[root<<1|1];}void pushdown(int root, int lenl, int lenr) { if (lazy[root] == 0) return; lazy[root<<1] += lazy[root]; lazy[root<<1|1] += lazy[root]; a[root<<1] += lazy[root]*lenl; a[root<<1|1] += lazy[root]*lenr; lazy[root] = 0;}void build(int l, int r, int root) { a[root] = lazy[root] = 0; if (l == r) return; int mid = (l + r)>>1; build(l, mid, root<<1); build(mid+1, r, root<<1|1); pushup(root);}void update(int l, int r, int root, int ul, int ur, int v) { if (ul <= l && r <= ur) { a[root] += v; lazy[root] += v; return; } int mid = (l + r)>>1; pushdown(root, mid-l+1, r-mid); if (ul <= mid) update(l, mid, root<<1, ul, ur, v); if (mid < ur) update(mid+1, r, root<<1|1, ul, ur, v); pushup(root);}ll query(int l, int r, int root, int p) { if (l == r) return a[root]; int mid = (l + r)>>1; pushdown(root, mid-l+1, r-mid); if (p <= mid) return query(l, mid, root<<1, p); else return query(mid+1, r, root<<1|1, p);}void dfs(int f, int u, int d) { for (int i = 0; i < vec[u].size(); i++) { update(1, n, 1, d, min(n, d+vec[u][i].first), vec[u][i].second); } res[u] = query(1, n, 1, d); for (int i = head[u]; ~i; i = edges[i].next) { int v = edges[i].to; if (v == f) continue; dfs(u, v, d+1); } for (int i = 0; i < vec[u].size(); i++) { update(1, n, 1, d, min(n, d+vec[u][i].first), -vec[u][i].second); }}int main() { scanf("%d", &n); tot = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < n-1; i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); addedge(v, u); } scanf("%d", &m); for (int i = 0; i <= n; i++) vec[i].clear(); for (int i = 0; i < m; i++) { int v, d, x; scanf("%d %d %d", &v, &d, &x); vec[v].push_back(make_pair(d, x)); } dfs(-1, 1, 1); for (int i = 1; i <= n; i++) { printf("%I64d", res[i]); if (i == n) printf("\n"); else printf(" "); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。