[蓝桥杯学习]树的直径与重心

树的直径

定义

为什么不直接说（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的子树(把树看成一个无向图)

性质

如何求重心