BZOJ-3626:LCA(离线+树链剖分)
2024-09-18 04:18:16
Description
给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。
(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)
Input
第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。
Output
输出q行,每行表示一个询问的答案。每个答案对201314取模输出
Sample Input
5 2
0
0
1
1
1 4 3
1 4 2
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
5
HINT
共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。
思路:发现很难做,转化为差分。每个询问[x,y]与z的LCA和拆分两个三元组(x-1,z,-1)和(y,z,1);我们从1到N加点,每加一个点,就把它到根的值++,然后回答对应的三元组,累加到三元组对应的答案里去。比如加点到[1,i],如果有三元组(i,x,1),那么就用累加x到根的权值,用树剖即可。
最新文章
- 【原】让H5页面适配移动设备全家 - 设计师篇 - PPT
- 推荐12个漂亮的 CSS3 按钮实现方案
- 【问题解决】线程间操作无效:从不是创建控件“textBox1”的线程访问它
- Python绘图和数值工具:matplotlib 和 numpy下载与使用
- MyBatis报错
- 自定义input file样式
- 小米2s刷机
- 关于jquery的$each((Object, function(p1, p2)用法
- RecyclerView线性分割线
- Bash 常用快捷键(转)
- C#中windows服务安装方法
- [SDOI2013]森林 主席树+启发式合并
- jq判断是PC还是手机端的方法
- 【安全性测试】drozer中关于AttackSurface的一些理解
- 在多机器上远程执行JMeter
- matlab练习程序(求向量间的旋转矩阵与四元数)
- luogu 3790 文艺数学题 - 矩阵树定理 - 容斥原理
- 快排 - 快速排序算法 (Chinar出品 简单易懂)
- 多线程的使用:只能用cmd来玩不能用idle
- 面向对象SOLID原则的自我理解