centroid

对于一个不是重心的点 \(u\)，它必定有一棵子树 \(T\) 包含所有重心（如果有两个重心则它们必定相邻），显然 \(|T|>\lfloor\frac{n}{2}\rfloor\)，这阻碍了它成为重心。贪心地想，我们要在 \(T\) 中找出一棵子树 \(S\) 使得 \(|S|\leq\lfloo ......

2023-10-06 题目 Centroid Probabilities 难度&重要性(1~10):8 题目来源 luogu 题目算法 组合数学，dp 解题思路 首先我们需要处理一下如何去满足好树的条件。很容易想到，当我们定点 \(1\) 为根节点时，每次让结点编号小的当结点编号大的父亲。这样我们就 ......

质心插值说的是什么 2023.10.04再次review这个细节点： https://www.opengl.org/pipeline/article/vol003_6/ https://github.com/WebGLSamples/WebGL2Samples/blob/master/samples ......

## Two Centroids 先考虑对于一棵树，至少要加多少个点才能有两个重心。 以重心为根，设最大儿子的子树大小为 $mx$，那么答案就为 $(n - mx) - mx = n - 2mx$。 接下来考虑如何在加点时维护最大子树，一个显然的性质，加一个点重心最多偏移一位，如果重心偏移，那么 $ ......

生生动动贺题贺一遍！ 考虑先求出 $f_x$ 表示 $x$ 子树大小 $\leq \frac{n + 1}{2}$ 的方案数。 最后再容斥掉 $x + 1 \to n$ 的方案即可。 $$\huge f_x = \sum^{n - x + 1}_{j = \frac{n + 1}{2}} \bino ......

CF708C Centroids 一道换根 DP。 我们可以先找出树的一个重心，那么对于其他所有不是重心的点，它不能成为重心时因为它父亲的那一支节点数大于一半，而可以改造成功，则意味着可以在他父亲那一支里，可以找到子树u，使 $siz[u] \le n/2 && siz[fa]-siz[u] \le ......

洛谷传送门 CF 传送门 考虑固定一个重心，设 $k$ 为重心最大子树大小，答案为 $n - 2k$。构造方法是往最大的子树塞叶子。 树的重心有一个很好的性质，就是加一个叶子，重心最多移动一条边的距离。简单证一下，设重心为 $x$，往儿子 $u$ 的子树中加叶子。 如果 $sz_u > \left\ ......

题意： 给定一颗树，你有一次将树改造的机会，改造的意思是删去一条边，再加入一条边，保证改造后还是一棵树。 请问有多少点可以通过改造，成为这颗树的重心？（如果以某个点为根，每个子树的大小都不大于$\dfrac{n}{2}$，则称某个点为重心） 思路： 是今天遇到的一道有意思的换根dp呃呃。 从题意来看 ......

摘要： 本文说首次实现了大规模点云场景中基于点的模型的实时检测（<30ms）; 首先指出FPS采样策略进行下采样是耗时的，尤其当点云增加的时候，计算量和推理时间快速增加； 本文提出IC-FPS；包含两个模块：local feature diffusion based background point ......