树的直径
定义
给定一棵树,始终每条边都有一个权值,树中两点间的距离定义为连接两点间的路径上的边权之和.树中最远的两个点间的距离被称为树的直径,连接这两个点的路径被称作树的最长链,通常也可称为直径.因此,直径既是一个数值,也代表一条路径
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。树的直径有两种求法,时间复杂度都是$O(N)$,我们假使树以$N$个点,$N-1$条边的无向图形式给出,并存储在邻接表中
树形$DP$求树的直径
不妨以$1$号节点为根,"$N$个点$N-1$条边的无向连通图"就可以看作"有根树".
设$D[x]$表示从节点$x$出发走向以$x$为根的子树,能够到达的最远节点的距离.设$x$的子节点为$y1,y1,y3,...,y_t$,$edge(x,y)$表示边权,显然有:
$D[x]=\mathop{max}\limits_{1 \leqslant i \leqslant t} {D[y_i]+edge(x,y)}$
接下来,我们可以考虑是对每个节点$x$,求出"经过$x$的最长链长度"$F[x]$,整棵树的直径就是$\mathop{max}\limits_{1 \leqslant j<i \leqslant t} {F[x]}$.
那么,如何求出$F[x]$呢?对于$x$的任意两个节点$y_i$和$y_j$,"经过节点$x$的最长链的长度"可以通过四部分组成:从$y_i$到$y_j$子树的最远距离,边$(x,y_i)$,边$(x,y_j)$
更多精彩
