重心
树的重心
const int N=100010; int n, a, b; vector<int> e[N];//用vector作邻接表 int siz[N], pos, ans=1e9; void dfs(int x, int fa){ siz[x]=1; int mx=0; for(auto y : e[ ......
重心法判断点是否在三角形内
1) 点在三角形的边上时 AP=AE+AF (向量加法) 设AE=v*AB, AF=u*AC; 则AP=v*AB+u*AC（二元一次方程，u, v为我们引入的变量） 根据向量三点共线定理可知：u+v=1 2) 点在三角形内时 AE不变, 让AF变短一些, 当用u*AC表示AF时, u的值肯定也比1) ......
树的重心讲解
1.定义 对于无根树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。 具体解释一下，如图给出的一棵树中 若以1为根节点，则它的子树为{2,4,5}和{3,6,7}，最大子树的节点数为3； 若以2为根节点，则它的子树为{4}，{5}和{1,3,6,7}，最大子树的节点数 ......
数学基础：三角形重心坐标插值公式的证明
在快速Phong明暗处理（Blinn-Phong明暗处理）时，出现了三角形重心坐标插值公式，但没有给出证明. 网上也鲜有证明过程，这里给出证明. 问题描述：在三角形ABC中，三顶点A、B、C坐标分别为\((x_1,y_1,z_1)、(x_2,y_2,z_2)、(x_3,y_3,z_3)\). 则三角 ......
P5666 [CSP-S2019] 树的重心
考虑一个结点在什么情况下会成为重心。 随便钦定一个根结点。对于结点 \(u\)，假设割掉了其子树 \(v\) 中的某条边或连接 \(u\) 和 \(v\) 的边，形成了一棵大小为 \(k\) 的新树。 令 \(mx\) 表示除 \(v\) 子树外最大的子树大小（或 \(n-siz_u\)）。如果 \ ......
关于三角形的四种心（外心，内心，重心，垂心）
外心 三条边垂直平分线的交点为外心。 到三顶点距离相等 内心 三条内角平分线的交点为内心。 到三条边的距离相等 同时是内切圆的圆心 重心 三条中心的交点为重心 同时是物理意义上的重心 公式：\(G(x_0,y_0),x_0=\frac{x_1+x_2+x_3}{3},y_0=\frac{y_1+y_ ......
树的直径、重心、中心
树的直径、重心、中心 一、树的直径 我们将一棵树 \(T=(V,E)\) 的直径定义为 $max(u,v)(u,v∈V) $，即树中所有最短路径距离的最大值即为树的直径。 求法： 1）树形dp 定义d1为从节点u到其子树中节点距离的最大值,d2为次大值,则\(diameter=max(d1+d2)\ ......
[CSP-S2019] 树的重心 题解
[CSP-S2019] 树的重心 因为这道题令我十分兴奋，所以来写一下做完后的思考。 这道题用到了树的重心的种种性质，在写解法的时候会一一点出其用处。 首先，枚举每一条边，然后各自 \(O(n)\) 扫一次的 \(O(n^2)\) 做法是简单的。 那么接下来，就会出现不同的解法了： 优化 \(O(n ......
我汤姆回来了（树和图的深度优先遍历（树的重心））（10/11）
#include<iostream> #include<cstring> using namespace std; const int N = 100010; const int M = N * 2;//可能多次节点重复，所以开大 int n; int e[M], ne[M], h[N], idx ......
树的重心
# [[CSP-S2019] 树的重心](https://www.luogu.com.cn/problem/P5666) 需要了解重心的很多性质： 1. 重心有 $1\sim 2$ 个，满足删除重心后形成的连通块最大大小 $\le \lfloor \dfrac{n}{2}\rfloor$，若有 $2 ......
树的重心
# [模板1：树的重心](https://wikioi.cn/problem/584) # [模板2：树的重心](https://www.acwing.com/problem/content/848/) 1求重心，2求重心删除后的最大连通块。 # 基本方法 对于每个点，我们计算一下它分离后的最大连通 ......
树的重心
树的重心：找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。使得以该节点为根的子树中，最大子树高度最小的节点 //会议 //https://www.luogu.com.cn/problem/P1395 // f数组：f数组用于记录以每个节 ......
FJOI 树的重心题解
**从零开始**~~暴切~~省选题 ## 题意简述 给定一个 $n$ 个点的树，每个点的编号从 $1$ 至 $n$，问这个树有多少不同的连通子树，和这个树有相同的重心。 ## 分析 #### 1 求重心 首先要明确重心的定义。题目中给出：删掉某点 $i$ 后，若剩余 $k$ 个连通分量，那么定义 $ ......
CF1824B2 LuoTianyi and the Floating Islands (Hard Version) - 概率期望 - 树的重心 -
题目链接：https://codeforces.com/contest/1824/problem/B2 题解： 考虑一棵 $n$ 个点的树，假如已经选定了 $k$ 个特殊点，如何判断某一个点是否为好点？ 显然将这个点提到根没有影响，那么好点的充要条件是对于所有子树的 $S_u$ 值都 $\leq k ......