点分治小结
点分治小结
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132217048
https://www.luogu.com.cn/problem/P3806
-
dfs1：找到当前重心
-
dfs2：统计当前每个点到重心的距离
-
dfz：点分治
找重心，处理出 所有儿子子树和非 子树的大小最大值，这个最大值最小的点 就是答案
注意这个过程中统计非 子树大小需要统计当前分治区间的大小 ，要时刻注意维护这个
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...
2022-01-24
【CF1120D Power Tree】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15839195.html 题目链接 题目 You are given a rooted tree with n n n vertices, the root of the tree is the vertex 1 1 1 . Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree 1 1 1 . Arkady ...
2023-08-10
颜色类问题与分治：P7215
颜色类问题与分治：P7215 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132221132 https://www.luogu.com.cn/problem/P7215 化为点分治后，把原问题变成钦定一个点必选的问题 转化这一步是点分治维护颜色类题目的一个性质，如果某种颜色外面有，就会在外面被考虑，不需要在此层 对朴素分治也有启发，对于在大区间统计了的答案，就不需要在小区间统计了 考虑在钦定一个点必选时，怎么做，首先把它定义为根。 把每种颜色丢入一个...
2022-05-18
【一本通1489：构造完全图】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16285749.html 题目链接 题目 对于完全图 GGG，若有且仅有一棵最小生成树为 TTT，则称完全图 GGG 是树 TTT 扩展出的。 给你一棵树 TTT，找出 TTT 能扩展出的边权和最小的完全图 GGG。 思路 要使一个图总存在唯一最小生成树，需满足所有非最小生成树的边（假设连接 u,vu,vu,v），使这条边的边权 www 大于 u,vu,vu,v 在最小生成树上的最短路径的最大边权。 因此，我们可以先dfs一遍求出每个点到根节点...
2023-08-03
欧拉回路/路径求法
欧拉回路/路径求法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132082624 以任意一点/奇数度点开始dfs，能走就走，遍历所有边，离开时加入点。 1234567void dfs(int x) { for(; t[x]<G[x].size(); ) { int y=G[x][t[x]]; ++t[x]; dfs(y); } z.push(x); }
2022-01-13
【CF6E Exposition】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15798330.html 题目链接 题目 There are several days left before the fiftieth birthday of a famous Berland's writer Berlbury. In this connection the local library decided to make an exposition of the works of this famous science-ficti...