搜索结果
查询Tags标签： 重心，共有 10条记录-
SP2420 题解
SP2420 solution给定一颗 \(n\) 个节点的树，在树上找一条长为 \(l\) 的链，使得树上每个节点到链的距离之和最短，求这个最短距离。题解 首先我们思考多个点到一个点距离和怎么计算。可以考虑使用树形 DP，将这个点作为跟，记录 \(siz_u\) 为 \(u\) 点子树的大小，\(sum_…
2022/8/13 23:28:53 人评论 次浏览 -
manacher算法 学习笔记
算法简介 这是一个可以在 \(O(n)\) 时间内求出一个字符串中所有子串的最长回文串长度。 求最长回文串长度的方法显然有多种，可以 \(O(n^2)\) 暴力，也可以枚举回文重心，二分回文串半径，哈希比较左右是否对称，这样是 \(O(n\log n)\) ，而这次是 \(O(n)\) 基本思路 设 \…
2022/7/29 14:22:43 人评论 次浏览 -
树上分治
1. 点分治 现在有一棵大小为 \(n\) 的树，要求出路径长度小于 \(k\) 的路径。 每次可以通过选择重心的方式，将整棵树分为一堆不大于 \(\dfrac{n}{2}\) 的子树，所以将整棵树分为大小为 \(1\) 的子树需要 \(\log n\) 次。 对于现在求出重心的子树，显然有三种情况可以组成…
2022/7/25 23:24:18 人评论 次浏览 -
洛谷P1364医院设置(树形DP)
医院设置本题给我们一棵树还有所有点之间的关系，要我们找到医院设在什么位置的时候，在所有节点上的人到医院所有走的距离和最小。要求的是所有点到某一个节点的距离和最小，我们可以想到树的重心。树的重心的定义是树若以某点为根，使得该树最大子树的结点数最小，那么这…
2022/4/15 23:13:02 人评论 次浏览 -
点分治
点分治常用于树上路径统计等问题。 点分治 每次分治过程大致如下：我们先求出当前连通块树的重心；处理与重心有关的答案；删除重心递归处理与重心相连的子连通块。伪代码如下： void solve(int x) {Find1(x,0),Find2(x,0); // 找到重心 rt // 处理和 rt 有关的答案used[r…
2021/11/27 23:11:08 人评论 次浏览 -
点分治
点分治常用于树上路径统计等问题。 点分治 每次分治过程大致如下：我们先求出当前连通块树的重心；处理与重心有关的答案；删除重心递归处理与重心相连的子连通块。伪代码如下： void solve(int x) {Find1(x,0),Find2(x,0); // 找到重心 rt // 处理和 rt 有关的答案used[r…
2021/11/27 23:11:08 人评论 次浏览 -
树的重心
树的重心 定义: 重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。 不妨设max_part(x)为在删除节点x后产生的子树中，最大的一颗大小。那么树的重心就是使得max_part函数取到最小的节点p就是整颗树的重心。 v…
2021/10/22 6:09:42 人评论 次浏览 -
树的重心
树的重心 定义: 重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。 不妨设max_part(x)为在删除节点x后产生的子树中，最大的一颗大小。那么树的重心就是使得max_part函数取到最小的节点p就是整颗树的重心。 v…
2021/10/22 6:09:42 人评论 次浏览 -
平面中判断点在三角形内算法(重心法)
文章目录 1. 概述2. 详论2.1. 原理2.2. 实现2.3. 总结 3. 参考1. 概述 在文章《判断点是否在三角形内》中还提到了一种判断点在三角形内外的算法——重心法。这种算法同样用到了三角形的空间向量方程，但是值得注意的是，这种算法却只能判断平面中点在三角形的内外关系(已…
2021/6/12 20:51:21 人评论 次浏览 -
平面中判断点在三角形内算法(重心法)
目录1. 概述2. 详论2.1. 原理2.2. 实现2.3. 总结3. 参考 1. 概述 在文章《判断点是否在三角形内》中还提到了一种判断点在三角形内外的算法——重心法。这种算法同样用到了三角形的空间向量方程，但是值得注意的是，这种算法却只能判断平面中点在三角形的内外关系(已知空间…
2021/6/12 20:51:15 人评论 次浏览
