SP10707 COT2 - Count on a tree II [树上莫队学习笔记]
2024-10-08 08:10:01
树上莫队就是把莫队搬到树上…利用欧拉序乱搞。。
子树自然是普通莫队轻松解决了
链上的话 只能用树上莫队了吧。。
考虑多种情况
[X=LCA(X,Y)]
[Y=LCA(X,Y)]
else
void dfs(int u) {
sz[u] = 1 ; rev[st[u] = ++ cnt] = u ;
for(int i = 0 ; i < G[u].size() ; i ++) {
int v = G[u][i] ;
if(v == fa[u]) { continue ; }
fa[v] = u ; dep[v] = dep[u] + 1 ;
dfs(v) ; sz[u] += sz[v] ;
if(sz[v] > sz[son[u]]) son[u] = v ;
}
rev[ed[u] = ++ cnt] = u ;
}
首先呢 \(st[lca]\leq st[x],st[lca]\leq st[y]\)
那么为了方便下面的表示都是 \(st_x < st_y\)
如果 \(x\) 不是 \((x,y)\) 的LCA 那么就GG了 额外统计 LCA 的贡献
if(lca == x) { q[i].l = st[x] ; q[i].r = st[y] ; }
else { q[i].l = ed[x] ; q[i].r = st[y] ; q[i].lca = lca ; }
大概长这个样子吧。。
sort(q + 1 , q + Q + 1) ;
int l = 1 , r = 0 ;
for(int i = 1 ; i <= Q ; i ++) {
while(l > q[i].l) { Add(rev[-- l]) ; }
while(r < q[i].r) { Add(rev[++ r]) ; }
while(l < q[i].l) { Add(rev[l ++]) ; }
while(r > q[i].r) { Add(rev[r --]) ; }
if(q[i].lca) { Add(q[i].lca) ; }
Ans[q[i].id] = ans ;
if(q[i].lca) { Add(q[i].lca) ; }
}
最新文章
- .Net 开源项目资源大全
- Windows Phone 8.1低功耗蓝牙开发-Nokia Treasure Tag
- wrong requestcode when using startActivityForResult
- chrome调试找不到 XXXX.min.map 原因及解决办法
- 转载-python学习笔记之输入输出功能读取和写入数据
- Best JavaScript Tools for Developers
- MySQL数据库安装(CentOS操作系统/tar.gz方式)
- iOS中 自定义cell分割线/分割线偏移 韩俊强的博客
- 证明与计算(1): Decision Problem, Formal Language L, P and NP
- kail linux虚拟机安装tools工具
- django(channel)到 ubuntu
- Winfrom BackgroundWorker
- python面试中被问的最多的10道题
- python笔记31-使用ddt报告出现dict() ->; new empty dictionary dict(mapping) 问题解决
- HDU - 1542 扫描线入门+线段树离散化
- 35. Oracle监听器启动出错:本地计算机上的OracleOraDb11g_home1TNSListener服务启动后又停止了解决方案
- ubuntu14.04 LTS Python IDE专用编辑器PyCharm开发环境搭建
- 数据读取速度达1.5G/s,UFS 2.1存储技术曝光
- JQuery包装集size,length,index,slice,find,filter,is,children,next,nextAll,parent,parents,closest,siblings,add,end,andSelf的用法
- php中类和对象的操作
热门文章
- Lambda 表达式入门,看这篇就够了
- 技术派-如果编译提示winnt.h(222):error C2146错误
- LESS 用法入门
- 构建一个学生Student,根据类Student的定义,创建五个该类的对象,输出每个学生的信息,计算并输出这五个学生Java语言成绩的平均值,以及计算并输出他们Java语言成绩的最大值和最小值。
- MybatisDao
- Codeforces_813
- HDU_3853_概率dp
- 调用caffe脚本将图片转换为了lmdb格式
- java4选择结构 二
- NR / 5G - Downlink Carrier Waveform