简单树上问题

1. 树的重心

树的重心是无根树上的一个应用。满足以下性质的点 \(u\) 为树的重心：

删除结点 \(u\) 即与它相连的边，如果在剩下的两棵或多课子树中最大子树的结点数最少，那么 \(u\) 就是树的重心。

例1 POJ-3107 翻译

本题的教父就是树的重心。接下来分析方法。

首先是暴力法。枚举一个点，设它为重心，计算出删除它后剩下的子树中最大子树的结点数来判断是否合法。计算节点数时可以用 DFS。这样时间复杂度为 \(\mathcal{O}(N^2)\)，不能通过本题。

只需要做一次 DFS 就可以求解。

设结点 \(1\) 为根。用 \(S_i\) 表示结点 \(i\) 的子树的结点数，这样 \(S\) 可以用一次 DFS 求出。那么去掉结点 \(u\) 后，\(u\) 的所有子节点会成为单独的树，它们的大小在 DFS 的过程中已经求出；\(u\) 的父节点也会成为一棵单独的树，它的大小即为 \(n-S_u\)。这样就可以在一次 DFS 的同时求出树的重心了。

代码

2. 树的直径

树的直径是指树上最远的两点之间的距离。有两种方法求树的直径：

1. 两次 DFS 或 BFS。

2. 树形 DP。

这两种方法的时间复杂度都为 \(\mathcal{O}(N)\)。

方法 \(1\) 可以记录路径，但不能处理负边权。

方法 \(2\) 可以处理负边权，但不能记录路径。

1. 两次 DFS 或 BFS

例1 洛谷-U283565

DFS 或 BFS 可以处理没有负边的树。方法很简单：

• 在树上找任意一点为起点，用 DFS 求出到这个点距离最远的点 \(s\)。

• 接下来以 \(s\) 为起点，用 DFS 求出到 \(s\) 最远的点 \(t\)。

• \(s,t\) 即为树的直径的两个端点。

代码

2. 树形 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\) 就会更新成最大值。

于是就不用再排序了。

例2 洛谷-U81904

本题边权有负数，应使用树形 DP。

代码

3. 习题

Baekjoon-1167 翻译

本题链式前向星似乎不能通过，但邻接表可以通过。建单向边。

Baekjoon-1967 翻译

本题数据规模较小且没有负权值。建单向边。