1. 树的重心
树的重心是无根树上的一个应用。满足以下性质的点 \(u\) 为树的重心:
删除结点 \(u\) 即与它相连的边,如果在剩下的两棵或多课子树中最大子树的结点数最少,那么 \(u\) 就是树的重心。
本题的教父就是树的重心。接下来分析方法。
首先是暴力法。枚举一个点,设它为重心,计算出删除它后剩下的子树中最大子树的结点数来判断是否合法。计算节点数时可以用 DFS。这样时间复杂度为 \(\mathcal{O}(N^2)\),不能通过本题。
只需要做一次 DFS 就可以求解。
设结点 \(1\) 为根。用 \(S_i\) 表示结点 \(i\) 的子树的结点数,这样 \(S\) 可以用一次 DFS 求出。那么去掉结点 \(u\) 后,\(u\) 的所有子节点会成为单独的树,它们的大小在 DFS 的过程中已经求出;\(u\) 的父节点也会成为一棵单独的树,它的大小即为 \(n-S_u\)。这样就可以在一次 DFS 的同时求出树的重心了。
2. 树的直径
树的直径是指树上最远的两点之间的距离。有两种方法求树的直径:
-
两次 DFS 或 BFS。
-
树形 DP。
这两种方法的时间复杂度都为 \(\mathcal{O}(N)\)。
方法 \(1\) 可以记录路径,但不能处理负边权。
方法 \(2\) 可以处理负边权,但不能记录路径。
- 两次 DFS 或 BFS
DFS 或 BFS 可以处理没有负边的树。方法很简单:
-
在树上找任意一点为起点,用 DFS 求出到这个点距离最远的点 \(s\)。
-
接下来以 \(s\) 为起点,用 DFS 求出到 \(s\) 最远的点 \(t\)。
-
\(s,t\) 即为树的直径的两个端点。
- 树形 DP
设 \(dp_u\) 表示 \(u\) 的子树中距离 \(u\) 最远的点的距离。那么状态转移方程如下:
\(dp_u=\max(dp_v+w)\),其中 \(v\) 是与 \(u\) 相连的点,\(w\) 是 \(u\) 到 \(v\) 边的权值。
再用 \(f_u\) 表示经过点 \(u\) 的最长路径长度。那么状态转移方程如下:
\(f_u=\max(dp_u+dp_v+w)\),其中 \(dp_u\) 不包括 \(dp_v\) 子树的长度。
那么这颗树的直径即为 \(\max \limits_{i=1}^n f_i\)。
其实 \(f\) 不用单独开数组,只需要在每次计算出后取最大值即可。
那怎么计算不包括子树 \(dp_v\) 的 \(dp_u\) 呢?
可以发现,子树 \(u\) 内的最大值即为所有的 \(dp_v+w\) 的最大值与次大值之和。那么又分两种情况:
- 最大值在次大值之前被计算
在计算到次大值时,\(dp_u\) 为最大值,\(dp_u+dp_v+w\) 即为子树 \(u\) 最大值。
- 次大值在最大值之前被计算
在计算到次大值时,\(dp_u\) 为次大值,\(dp_u+dp_v+w\) 即为子树 \(u\) 最大值。接下来 \(dp_u\) 就会更新成最大值。
于是就不用再排序了。
本题边权有负数,应使用树形 DP。
3. 习题
本题链式前向星似乎不能通过,但邻接表可以通过。建单向边。
本题数据规模较小且没有负权值。建单向边。
标签:结点,子树,最大值,大值,DFS,问题,简单,树上,dp From: https://www.cnblogs.com/lrxmg139/p/18005717