传送门

对于每个点离线处理出向上走2i2^i2i班车到的最上面的点。

然后每个询问(u,v)(u,v)(u,v)先把(u,v)(u,v)(u,v)倍增到刚好走不到lcalcalca的情况(有一个点如果就是lcalcalca直接特判)

然后考虑最后把(u′,v′)(u',v')(u′,v′)连起来需要走一次还是两次。

这个就是一个二维数点问题了。

用dfsdfsdfs序求出每个点管辖的子树表示的区间。

然后对于询问(a,b)(a,b)(a,b)在dfs到aaa时统计bbb子树的答案。

把aaa子树的修改操作更新之后再统计一次bbb子树的答案。

如果两次答案一样说明某个端点在aaa子树中的班车对bbb子树均没有影响。

这样需要走2次，否则只用走1次。

代码

最新文章

1. Apache启动错误解决方法
2. Maven创建工程 WEB
3. Codeforces Round #325 (Div. 1) D. Lizard Era: Beginning
4. E.164 Format
5. Y5V贴片电容(MLCC)容量范围速查表
6. Zabbix(一) : 简介以及Server端安装
7. 使用dlib中的深度残差网络(ResNet)实现实时人脸识别
8. kafka--- consumer 消费消息
9. java没有firendly访问类型
10. 002_Python多线程相当于单核多线程的论证
11. me
12. 语音识别ASR - HTK(HResults)计算字错率WER、句错率SER
13. windows下consul利用json文件注册服务
14. form编码方式application/x-www-form-urlencoded和multipart/form-data的区别
15. Javascript 定时器调用传递参数的方法
16. golang xorm框架的使用
17. 陌生的 metaclass（转）
18. 2013级计算机学院数字媒体专业李成梁（笛卡尔积，概率树状图）& 学生选课
19. 在windows下安装配置python开发环境及Ulipad开发工具（转）
20. JTemplate学习（二）

热门文章

1. h5外部浏览器直接调起app
2. thinkphp 查找表并返回结果
3. linux虚拟机ping不通主机和外网（包括刚装系统遇到的一些问题）
4. 弹出PopupWindow背景变暗的实现
5. Mysql数据备份与还原
6. python re正则
7. Linux CentOS 7 下 Apache Tomcat 7 安装与配置
8. Andriod——手机尺寸相关的概念 +尺寸单位+关于颜色
9. javascript 高级程序设计 一
10. less 官网讲解 （ http://www.bootcss.com/p/lesscss/ ）