双带权重心？
枚举分解点x，x子树内找到一个，x子树外找到一个
考虑一般的操作是贪心移动，与子树总权值有关系
所以不妨按照子树权值进行树链剖分
那么一个点子树内的重心一定在重链上。
从重儿子贪心往上走即可
子树外？
设子树外所有点权值总和是c
先倍增二分找到第一个扣除x的子树总权值之后权值>c/2的
再从这个子树的重链往下走，找到第一个子树权值>c/2的。用线段树二分实现
但是bzoj卡空间，然后咕了。
代码.cpp
找重心：贪心移动，权值树剖！
双信息：枚举分割点
bzoj3068: 小白树
本文共 299 字，大约阅读时间需要 1 分钟。
转载于:https://www.cnblogs.com/Miracevin/p/10834686.html
你可能感兴趣的文章
组策略 从入门到精通 （七） 组策略的继承
查看>>
网站开发人员应该知道的62件事
查看>>
mybatis插入数据库时的问题记录
查看>>
Maven项目pom.xml文件报错“web.xml is missing and <failOnMissingWebXml> is set to true”
查看>>
docker入门之简单的容器使用
查看>>
系统架构相关概念辨析（一）
查看>>
关于java加密
查看>>
thinkphp3.2的行为
查看>>
PHP中使用Redis接管文件存储Session详解
查看>>
前后端如何优化网站性能
查看>>
js bind实现
查看>>
手工安装hadoop ecosystem之疑难杂症
查看>>
数论学习之（一）：一元线性同余方程和二元一次不等式
查看>>
SVM-支持向量机算法概述
查看>>
我的友情链接
查看>>
web容器启动时，借助spring进行初始化操作
查看>>
DNS服务器之BIND基础服务部署
查看>>
location
查看>>
Araxis Merge的help
查看>>
通过进程ID得到进程名
查看>>