洛谷3833 [SHOI2012]魔法树
SHOI2012 D2T3
题目描述
Harry Potter 新学了一种魔法:可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树,来试验他的新法术。
这棵果树共有N个节点,其中节点0是根节点,每个节点u的父亲记为fa[u],保证有fa[u] < u。初始时,这棵果树上的果子都被 Dumbledore 用魔法清除掉了,所以这个果树的每个节点上都没有果子(即0个果子)。
不幸的是,Harry 的法术学得不到位,只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说,Harry 的魔法可以这样描述:
Add u v d
表示将点u和v之间的路径上的所有节点的果子个数都加上d。
接下来,为了方便检验 Harry 的魔法是否成功,你需要告诉他在释放魔法的过程中的一些有关果树的信息:
Query u
表示当前果树中,以点u为根的子树中,总共有多少个果子?
输入输出格式
输入格式:
第一行一个正整数N (1 ≤ N ≤ 100000),表示果树的节点总数,节点以0,1,…,N − 1标号,0一定代表根节点。
接下来N − 1行,每行两个整数a,b (0 ≤ a < b < N),表示a是b的父亲。
接下来是一个正整数Q(1 ≤ ? ≤ 100000),表示共有Q次操作。
后面跟着Q行,每行是以下两种中的一种:
A u v d,表示将u到v的路径上的所有节点的果子数加上d;0 ≤ u,v <N,0 < d < 100000
- Q u,表示询问以u为根的子树中的总果子数,注意是包括u本身的。
输出格式:
对于所有的Query操作,依次输出询问的答案,每行一个。答案可能会超过2^32 ,但不会超过10^15 。
输入输出样例
4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2
3
3
2
思路
查询子树和就是查询DFS序的相应区间,难在修改。<- 这好像是句废话。
修改链的和,当然要树链剖分。
想到我之前写的一篇博客,树链剖分思想的LCA 链接 (按重链向上移动的套路)
这个修改就是用了这种思想。
两次DFS预处理出size,重链,DFS序。
细节:DFS儿子时要先走size最大的,确保重链上的DFS序编号是连续的,这样才能修改。
void DFS1(int x){
siz[x]=;
for(int i=last[x];i;i=e[i].pre){
int to=e[i].other;
if(f[x]==to)continue;
f[to]=x;depth[to]=depth[x]+;
DFS1(to);
siz[x]+=siz[to];
}
}
void DFS2(int x,int t){
vis[x]=;
int v=;
pos[x]=(++c2);top[x]=t;
for(int i=last[x];i;i=e[i].pre){
int to=e[i].other;
if(siz[to]>siz[v]&&depth[to]>depth[x])v=to;
}
if(!v)return;
DFS2(v,t);
for(int i=last[x];i;i=e[i].pre){
int to=e[i].other;
if(depth[x]>depth[to]||vis[to])continue;
DFS2(to,to);
}
}
修改,类似于之前找LCA的操作, 往上跳,区间修改 (Modify),
if(s[]=='A'){
int x=read(),y=read();long long z=read();x++,y++;
for(;top[x]!=top[y];x=f[top[x]]){
if(depth[top[x]]<depth[top[y]])swap(x,y);
Modify(,pos[top[x]],pos[x],z);
}
if(depth[x]<depth[y])swap(x,y);
Modify(,pos[y],pos[x],z);
后记
感觉线段树算是会了点了。
再水两道换东西了。
最新文章
- Log4net入门(回滚日志文件篇)
- Linux命令行下编译Android NDK的示例代码
- Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
- SQL 集合(笔记)
- STM32 USB-HID通信移植步骤
- 1008: [HNOI2008]越狱
- dos攻击与防御
- android开发必备日志打印工具类
- java基础之导入(Excel)2
- 从入门到放弃,.net构建博客系统(一):系统构建篇
- 【平板电脑模拟器】PC端-Chrome自带的功能
- java 5年规划---
- python爬虫的重定向问题
- element-ui对话框组件Dialog在回调事件opened获取组件滚动条scrollTop的问题
- BOM 浏览器对象模型_window 对象的常见 window.属性_window.方法
- latex 双引号 “
- Java 装箱和拆箱
- 性能测试九:jmeter进阶之beanshell的使用+断言
- 弄清SDI显示工程中的每一个信号,每一个逻辑
- HDU 4587 TWO NODES(割两个点的最大连通分支数)