本文主要是介绍[蓝桥杯学习]树的直径与重心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树的直径
定义
为什么不直接说（u,v）是两个叶子，可能有如下情况：
这是一条链，且u为根，但，度数为1
下面这个情况是不经过根的。
求解方法
如果设根u的深度为0时，直径就是深度dep[v]+1
例题
（后面不小心把c都写成m了。。。。不想改就这样吧）
收益有两种情况，以上图的树为例
第一种，往右边走，每向下一步，花费m，同时价值增加k。这时候要算总价值的话，就是求到右边点的最深的（这一部分的特征是：路径上没有直径上的点）
第二种，往左边走，在到达LCA之前，是一直在花费m且价值减少k，到达LCA之后，向着没有最深结点的方向走，这时花费m，同时价值增加k。算总价值的话，要到沿直径链到最深点。
下面直观来看
把这两种情况分别计算
不走直径的路：dep[u]*k+maxdep*(k-m)
原树根最深的点*边长+原树根不走直径最深的点的深度*（k-m）
走直径的路：depU[v]*k-dep[v]*m
直径长*k-原树根到非最深点的链端的深度*m （其中直径长是：以原根最深点为根到其它点的最深深度）
树的重心
定义
mss[x] 表示所有子树大小的最大值
注意：认为除去x及其子树剩余部分也是x的子树(把树看成一个无向图)
性质
如何求重心
这篇关于[蓝桥杯学习]树的直径与重心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
