洛谷$P$3241 开店 $[HNOI2015]$ 主席树/点分治
2024-10-08 03:43:58
正解:主席树/动态点分治
解题报告:
$umm$淀粉质的话要是动态的我还不会$QAQ$,,,所以先写下主席树的题解昂$QwQ$
题目大意是说,给定一棵树,树上每个点都有个值,然后有若干个询问,每次询问给定三个值,$(u,l,r)$,表示求值大小在$[l,r]$范围内的所有点到$u$点的距离之和是多少
考虑如果没有这个$[l,r]$的限制,就只是说,有若干个询问,每次给定一个$u$,问树上所有点到$u$的距离,怎么搞$QwQ$?
考虑固定一个点为根节点$rt$,预处理一个各个节点到根节点的距离$dis$,不难想到答案就,$ans=\sum_{i=1}^{n}dis_{i}+n\cdot dis_{u}-2\cdot \sum_{i=1}^{n}dis_{lca(u,i)}$,挺显然的不解释辣$QAQ$
显然的是只要能快速求出$\sum_{i=1}^{n}dis_{lca(u,i)}$就好了鸭$QwQ$
考虑对根节点到$u$节点这条链上的每条路考虑会被统计到的次数$num_{i}$,然后这个$\sum$就会等于$\sum num_{i}\cdot dis_{i}$
关于这个$num$,可以考虑在树剖中,对每个点往上走,对经过的道路就$num++$
然后考虑到$[l,r]$的限制,于是就再套个主席树,就欧克辣$QwQ$
写得有点儿草率,,,然而不想写辣$QAQ$,就这样儿趴$QAQ$有时间再写$QAQ$
最新文章
- 关于opacity的兼容问题
- hdu 4647 - Another Graph Game(思路题)
- MVC项目实践,在三层架构下实现SportsStore-10,连接字符串的加密和解密
- Lintcode: Interval Sum
- 最长公共上升子序列(LICS) 模板
- qt 获取天气的接口
- linux下tar用法
- Linux实现SSH无密码登录(对目录权限的设置非常详细,可以参考一下)
- C#开发模式——单例模式
- [补档][JLOI 2017]聪明的燕姿
- Linux下的进程与线程(一)—— 进程概览
- Token令牌管理权限
- java的编译过程
- poj3889
- 小甲鱼python第二讲课后习题
- Delphi目录监控、目录监听
- 宇宙最帅叉叉——第三周博客 for 需求改进&;原型设计
- 买了本Delphi面向对象编程思想,正在看,产生些问题。
- Ubuntu中使用pip3报错
- 由于dns服务为启动导致的GI集群启动故障
热门文章
- Linux 网络原理及基础设置
- uva 11754 Code Feat (中国剩余定理)
- 不插字段,直接利用OracleSpatial计算
- E - Count on a tree 树上第K小
- 为 Ubuntu 18.04 添加开机自动加载 ntfs分区 功能
- Python type hints 之 Optional,Union
- H3C DCC概念
- Python--day62--使用Bootstrap样式的出版社
- uni-app 常用框架内置方法 更新中 .....
- [C++] WinAES的问题