I - Vasya and a Tree

CodeForces - 1076E

其实参考完别人的思路,写完程序交上去,还是没理解啥意思。。昨晚再仔细想了想。终于弄明白了(有可能不对

题意是有一棵树n个点,初始时候每个点权值都为0,m次修改,对v的叶子节点且距离小于d的都加上x

也就是v以下d层包括v自身都加上x 问最后每个点的权值

现在一想 用线段树来维护就是很自然的事了

但是要维护什么值呢

维护的就是某个深度上增加的值

先更新 后回溯取消更新

详见代码注释

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define lp p<<1
#define rp p<<1|1
#define ll long long
using namespace std;
const int maxn = 3e5 + ;
typedef pair<int, int> P;
int n, m;
int tot, head[maxn];
struct Edge{ int to, next; }edge[maxn<<];
vector<P> vec[maxn];
ll a[maxn<<], lazy[maxn<<], res[maxn];
inline void addedge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
inline void pushup(int p) {
a[p] = a[lp] + a[rp];
}
inline void pushdown(int p, int llen, int rlen) {
if (lazy[p]) {
lazy[lp] += lazy[p];
lazy[rp] += lazy[p];
a[lp] += lazy[p] * llen;
a[rp] += lazy[p] * rlen;
lazy[p] = ;
}
}
void build(int p, int l, int r) {
a[p] = lazy[p] = ;
if (l == r) return;
int mid = l + r >> ;
build(lp, l, mid);
build(rp, mid + , r);
pushup(p);
}
void update(int p, int l, int r, int x, int y, int z) {
if (x <= l && y >= r) {
a[p] += 1LL * z * (r - l + );
lazy[p] += z;
return;
}
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
if (x <= mid) update(lp, l, mid, x, y, z);
if (y > mid) update(rp, mid + , r, x, y, z);
pushup(p);
}
ll query(int p, int l, int r, int u) {
if (l == r) return a[p];
int mid = l + r >> ;
pushdown(p, mid - l + , r - mid);
if (u <= mid) return query(lp, l, mid, u);
return query(rp, mid + , r, u);
}
//截至这里 应该都是线段树的基本操作 没啥好说的
void dfs(int f, int u, int d) {
for (int i = , sz = vec[u].size(); i < sz; i++) {
// 因为线段树记录的是深度 所以就可以把当前结点以及深度差为k的全部更新一遍
update(, , n, d, min(n, d + vec[u][i].first), vec[u][i].second);
}
//接下来dfs遍历的时候的update操作不会影响到父节点了 所以可以直接query得到答案
res[u] = query(, , n, d);
for (int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if (v == f) continue;
// 深度位置是共享的 比如 1既连接2又连接3 上面更新了深度为1,2的 在线段树上 2代表的就是2和3的权值
dfs(u, v, d + );
}
for (int i = ; i < vec[u].size(); i++) {
//回溯取消标记
update(, , n, d, min(n, d + vec[u][i].first), -vec[u][i].second);
}
}
int main() {
scanf("%d", &n);
tot = ;
memset(head, -, sizeof(head));
for (int i = , u, v; i < n - ; i++) {
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
scanf("%d", &m);
while (m--) {
int v, d, x;
scanf("%d%d%d", &v, &d, &x);
vec[v].push_back(make_pair(d, x));
}
dfs(-, , );
for (int i = ; i <= n; i++) {
printf("%I64d", res[i]);
if (i == n) puts("");
else putchar(' ');
}
return ;
}

最新文章

  1. ie8 jquery parents() 获取多个的问题
  2. Microsoft.Office.Interop.Word 创建word
  3. Verilog学习笔记认识提升篇(一)...............时序的基本概念(待补充)
  4. JavaEE基础(二十四)/多线程
  5. hdu 5565 Clarke and baton 二分
  6. php中引用符号(&amp;amp;)的使用详解
  7. python 遍历字典
  8. Hdu 1059 Dividing &amp; Zoj 1149 &amp; poj 1014 Dividing(多重背包)
  9. 男同胞爱小秘籍--作为爱他的女朋友了几天C规划
  10. 《编程人生:15位软件先驱访谈录》【PDF】下载
  11. 如何用Fritzing实现元器件自定义接线图
  12. 网络编程之socketserver
  13. 有终将被编程潮流淹没的程序员,那是因为没学python人工智能吧?
  14. CentOS7下MySQL5.7安装配置方法图文教程(YUM)
  15. 粉红猪小妹peppa pig中英文版209集+218本绘本+音频
  16. boost-使用说明
  17. package.json浅谈
  18. Eclipse设置方法模板
  19. os.path 模块
  20. 在Android Studio中创建项目和模拟器

热门文章

  1. SimpleDialogBox
  2. Java入门篇(五)——字符串/String类
  3. PHP中静态变量和函数引用返回
  4. 关于 HTTP GET/POST 请求参数长度最大值的一个理解误区(转载)
  5. H5 34-背景图片
  6. ASP.NET项目开发
  7. C#跨进程读取listview控件中的数据
  8. javaScript 删除本地cookie删不了
  9. 【学习总结】C-翁恺老师-入门-第0周&lt;程序设计与C&gt;
  10. Linux reboot与init 6区别