树的重心
树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
重心的性质：
树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心，他们的距离和一样。把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。一棵树最多有两个重心，且相邻。
我们求解树的重心也非常简单，我们还是以任意点的起点，找到一这个点为根的每个点的子树的数量，然后从中找一个最小值就行了，当然我们这里最好去维护一个每个节点与之有关联的节点的节点数，因为有可能是无根树。
#include
using namespace std;
vector
int son[100010],ans[100010],n;
int minn=INT_MAX,place;
void dfs(int x,int fa){
son[x]=1;
for (int i=0;i int tmp=mp[x][i]; if (tmp!=fa){ dfs(tmp,x); son[x]+=son[tmp]; ans[x]=max(ans[x],son[tmp]); } } ans[x]=max(ans[x],n-son[x]); } int main(){ cin>>n; for (int i=1;i int u,v; cin>>u>>v; mp[u].push_back(v); mp[v].push_back(u); } dfs(1,0); for (int i=1;i<=n;i++){ if (ans[i] minn=ans[i]; place=i; } } cout< return 0; } 带权树的重心 这其实和洛谷的医院设置差不多，所以我们就以医院设置这道题来 医院设置 题目描述 设有一棵二叉树，如图： 其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 111。如上图中，若医院建在 111 处，则距离和 =4+12+2×20+2×40=136=4+12+2\times20+2\times40=136=4+12+2×20+2×40=136；若医院建在 333 处，则距离和 =4×2+13+20+40=81=4\times2+13+20+40=81=4×2+13+20+40=81。 输入格式 第一行一个整数 nnn，表示树的结点数。 接下来的 nnn 行每行描述了一个结点的状况，包含三个整数 w,u,vw, u, vw,u,v，其中 www 为居民人口数，uuu 为左链接（为 000 表示无链接），vvv 为右链接（为 000 表示无链接）。 输出格式 一个整数，表示最小距离和。 样例 #1 样例输入 #1 5 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0 样例输出 #1 81 提示 数据规模与约定 对于 100%100\%100% 的数据，保证 1≤n≤1001 \leq n \leq 1001≤n≤100，0≤u,v≤n0 \leq u, v \leq n0≤u,v≤n，1≤w≤1051 \leq w \leq 10^51≤w≤105。 定义几个数组： f[u]表示以u为根的总距离，size[u]表示以u为根的子树的大小（结点数，此题每个点要乘以权值，下文结点数均指此）。 显然，ans=min(f[i],1<=i<=n)ans=min(f[i],1<=i<=n)ans=min(f[i],1<=i<=n) 首先我们任意以一个点为根dfs一遍，求出以该点为根的总距离。方便起见，我们就以1为根。 接下来就是转移，对于每个u能达到的点v，有： f[v]=f[u]+size[1]−size[v]−size[v]f[v]=f[u]+size[1]−size[v]−size[v]f[v]=f[u]+size[1]−size[v]−size[v] 怎么来的呢？试想，当根从u变为v的时候，v的子树的所有节点原本的距离要到u，现在只要到v了，每个结点的距离都减少1，那么总距离就减少size[v]size[v]size[v]，同时，以v为根的子树以外的所有节点，原本只要到u就行了，现在要到v，每个节点的路程都增加了1，总路程就增加了size[1]−size[v]size[1]−size[v]size[1]−size[v]，其中size[1]就是我们预处理出来的整棵树的大小，减去size[v]size[v]size[v]就是除以v为根的子树以外的结点数。 最后取最小值，得解。时间复杂度O(n)O(n)O(n) #include using namespace std; vector int children[110],dp[110],value[110],minn=INT_MAX; void child (int x,int fa,int deep){ children[x]=value[x]; for (int i=0;i int tmp=mp[x][i]; if (tmp!=fa){ child(tmp,x,deep+1); children[x]+=children[tmp]; } } dp[1]+=deep*value[x]; } void dfs(int x,int fa){ for (int i=0;i int tmp=mp[x][i]; if (tmp!=fa){ dp[tmp]=dp[x]+children[1]-(2*children[tmp]); dfs(tmp,x); } } minn=min(minn,dp[x]); } int main(){ int n; cin>>n; for (int i=1;i<=n;i++){ int u,v,l; cin>>value[i]>>u>>v; if (u!=0){ mp[u].push_back(i); mp[i].push_back(u); } if (v!=0){ mp[v].push_back(i); mp[i].push_back(v); } } child(1,0,0); dfs(1,0); cout< return 0; } 树的中心 给定一棵 n 个节点的无根树（节点编号 0 至 (n−1），所有边长均为1，求出该树的直径长度。 定义树的中心为距离树上所有节点距离的最大值最小的节点（一棵树的中心可能不止一个） 解析： 根据树的直径中的一条性质：距离任意点最远的点一定是直径的一个端点。，我们可以有一下操作： 首先找到直径的两个端点，并标记出来，以下设为x,yx,yx,y从x,yx,yx,y两个叶子节点出发，计算到每一个点的距离此时每一个点都会有两个距离，取其中的最大值在这些最大值找到最小值，那么它就是树的中心（注：可能不止一个） #include using namespace std; int dis1[200010],a[200010],dis2[200010]; vector int st,ed,t; int maxn=0; void dfs(int x,int fa,int deep){ for (int i=0;i if (mp[x][i]!=fa){ dis1[mp[x][i]]=deep+1; if (maxn maxn=dis1[mp[x][i]]; t=mp[x][i]; } dfs(mp[x][i],x,deep+1); } } } int main(){ int n; cin>>n; for (int i=1;i cin>>a[i]; mp[a[i]].push_back(i); mp[i].push_back(a[i]); } dfs(1,-1,0); st=t; maxn=0; dfs(st,-1,0); ed=t; cout< for (int i=0;i<=n;i++){ dis2[i]=dis1[i]; } dfs(ed,-1,0); int minn=INT_MAX; for (int i=0;i dis2[i]=max(dis2[i],dis1[i]); minn=min(dis2[i],minn); } for (int i=0;i if (minn==dis2[i])cout< } return 0; } 带权树的直径 其实这个和普通的树的直径没什么区别，只是在增加长度的地方略微不同罢了 #include using namespace std; struct f{ int len,num; }; vector int dis[1000010],st; void dfs(int x,int fa){ for (int i=0;i f tmp=mp[x][i]; if (tmp.num!=fa){ dis[tmp.num]=dis[x]+tmp.len; if (dis[st] dfs(tmp.num,x); } } } int main(){ int n; cin>>n; for (int i=1;i int u,v,l; cin>>u>>v>>l; mp[u].push_back({l,v}); mp[v].push_back({l,u}); } dfs(1,0); dis[st]=0; dfs(st,0); cout< return 0; }