树的重心

 

定义

 



 

 

 

性质

 



 

 

利用性质1求树的重心

 

 

代码演示一

 

我感觉这个代码有毒,想哭,每次都用代码二,不过代码思想都一样

 

 

 

代码演示二

 

 

习题

 

洛谷1364医院设置:https://www.luogu.com.cn/problem/P1364

 

题解:https://axieyun.top/posts/c91d.html

 

牛客网保卫村庄:[保卫村庄 (nowcoder.com)](https://ac.nowcoder.com/acm/problem/214212)

 

题解:https://axieyun.top/posts/8419.html0

 

 

树的直径

 

 

定义


 

带权树上距离最远的两点


 

性质

 


1、直径两端点一点是叶子节点 2、距离任意点最远的点一定是直径的端点,这个基于贪心求直径方法的正确性可以得出 3、对于任意两棵树,如果第一棵树的直径两端点为(u,v),第二棵树直径的两端点为(x,y), 用一条边链接这两棵树,那么新树的直径一定是u,v,x,y,其中两个点。 4、若一棵树存在多条直径,那么这些直径交与一点且交点是这些直径的中点。 5、对于一棵树,如果在一个点的上接一个叶子节点,那么最多会改变直径的一个端点。


 

 

树的直径有两种求法

 

DFS利用性质二求解树的直径

 

 

树形DP

 

 

 

 

 

 

习题

 

海贼oj421直径:http://oj.haizeix.com/problem/421

 

题解 :https://axieyun.top/posts/cf35.html