树的直径
模板题。
定义
树的任意两点之间的最长简单路径。
求法
dfs 做法
从任意一个节点 dfs 到和其距离最远的节点，可以证明其为树的直径的一端。然后再以直径的一端 dfs 走到和其距离最远的节点即可得出答案。
若要记录直径路径的话只需在第二次 dfs 上记录每个节点的前驱即可。
inline void dfs(int x, int last) {
for(auto u : g[x])
if(u.v != last) {
d[u.v] = d[x] + u.w;
if(d[c] < d[u.v]) c = u.v;
fa[u.v] = x;
dfs(u.v, x);
}
}
//寻找直径端点
ans[++ cnt] = c, ans[++ cnt] = cc;
while(fa[c] != cc) c = fa[c], ans[++ cnt] = c;
//路径记录
- 注：本做法不适用于负边权。
dp 做法
设 \(d1_i\) 为从第 \(i\) 个节点出发可到达的最长路径长度，\(d2_i\) 为从第 \(i\) 个节点出发可到达的不与最长路径有重叠的次长路径长度。答案显然为 \(\max\{ d1_i + d2_i \}\)。
接下来考虑两个 dp 序列的转移。
\(d1\) 可以由其儿子的答案加上一条边的权和原本值的最大值来转移，具体地：
\[d1_x=\max\{ d1_x,d1_{u\in x} + w_{u,x} \} \]当 \(d1\) 变得更大了，\(d2\) 自然就继承了 \(d1\) 原本的值。而其儿子的答案加上一条边的权如果小于 \(d1\) 的话，就有可能会成为新的 \(d2\)。具体地：
\[d2_x = \begin{cases}d1_x\ d1_{u\in x} + w_{u,x} > d1_x\\\max\{ d2_x,d1_{u\in x} + w_{u,x} \}\ otherwise\end{cases} \]inline void dfs(int x, int last) {
for(auto u : g[x])
if(u.v != last) {
dfs(u.v, x);
int t = d1[u.v] + u.w;
if(t > d1[x]) d2[x] = d1[x], d1[x] = t;
else if(t > d2[x]) d2[x] = t;
}
}
性质
- 树的直径不一定唯一
- 树的直径若有多条，那么必交于一点，这一点必为直径的中点，也称之为树的中心（反证法证明）
- 树上任意点 \(x\) 距离其最远的点一定是直径的端点
- 两棵树连边，选择树的中心相连，新的树直径最小
- 树的题目的端点一定是度数为 \(1\) 的点
例题
CF1404B Tree Tag
- 步骤
分类讨论。
1.Alice 一步即可抓到 Bob：\(dis(a, b) \le da\)
2.\(db\le 2·da\)，即 Alice 必然会将 Bob 赶进某棵子树内，那么 Bob 就一定要在某个时刻折返，Alice 只要走 Bob 的一半距离以上即可
3.Alice 站在树的中心时，只需要覆盖最长链：\(\frac{diam}{2}\le da\)
维护树的直径即可。
CF455C Civilization
- 步骤
1.树的边权为 \(1\)，那么以树的中心为根的树的最长链长度为 \(\lceil \frac{diam}{2}\rceil\)
2.每次连边，连树的中心最优，则新树的直径为：
维护树的直径即可。
CF1294F Three Paths on a Tree
1.先考虑两个点，显然选直径的两端点
2.反证可以得到选三个点是必然会选树的直径的两个端点
3.无论第三个点 \(w\) 怎么选，可以认为 \(w\) 与 \(u,v\) 上的路径交于某点 \(p = LCA(w, v)\)
4.枚举 \(w\)，求 \(p = LCA(w, v)\)，\(w\) 到直径的距离为 \(dep_w - dep_v\)，所以答案为：
\[\max \left \{ diam + dep_w - dep_p \right \} \]维护 LCA 和树的直径即可。
还有一种做法是以直径上的每一个点跑 bfs 求最短路（血色先锋队）可以将时间复杂度优化至 \(O(n)\)。
树的重心
定义
以一个 \(x\) 节点为根时，其节点树最大的子树最小的 \(x\)。
性质
-
树的重心如果不唯一，则至多有两个，且这两个重心相邻。
-
以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。
-
树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
-
把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
-
在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。
求法
根据定义，我们用在搜索到每一个节点时求其每一个子树与 \(n/2\) 的大小关系。
需要注意的是因为我们在树上 dfs 时需钦定一个节点作为根的特殊性，我们要特判 \(n - sz_x\) 与 \(n / 2\) 的大小关系。（换根思想）
inline void get_ctr(int x, int last) {
sz[x] = 1;
for(auto u : g[x])
if(u != last) {
dfs(u, x);
sz[x] += sz[u];
mxs[x] = max(mxs[x], sz[u]);
}
mxs[x] = max(mxs[x], n - sz[x]);
if(mxz[x] << 1 <= n) ctr.pb(x);
}
例题
CF685B Kay and Snowflake
- 步骤：
1.从下往上处理每一个子树的重心
2.对于任意点 \(x\)，其所在子树的重心一定在 \(x\) 和 \(ans_u\) 之间，\(ans_u\) 表示 \(x\) 的最大子树 \(u\) 的重心节点
3.对于任意点 \(x\)，其所在的子树重心深度一定不大于 \(ans_u\)
4.跳倍增即可
关键代码：
inline void dfs(int x, int last) {
sz[x] = 1;
for(auto u : g[x])
if(u != last) {
dfs(u, x);
sz[x] += sz[u];
if(sz[u] > mxs[x]) mxs[x] = sz[u], son[x] = u;
}
mxs[x] = max(mxs[x], n - sz[x]);
int tmp = ans[son[x]];
if(! son[x]) {
ans[x] = x;
return;
}
while(sz[tmp] << 1 <= sz[x]) tmp = fa[tmp];
ans[x] = tmp;
}
某题
- 分析
1.每棵树内部点对贡献不变，只有经过新加边的点对才能影响结果
2.设新加边端点为 \(x, y\)，显然一棵树的所有点要走到 \(x\)，另一棵树的所有点要走到 \(y\)
3.贪心地想，新边应该连接两棵树的重心
4.连边后得到新树，枚举每条边，计算出每条边被经过的次数，再求和即为答案
5.维护 \(sz_x\) 表示以 \(x\) 为根的子树大小，那么经过 \(x\) 和 \(fa_x\) 这条边的次树为：\(sz_x\times (n - sz_x)\)
6.从点 \(1\) 开始找重心并标记节点，未被标记的就一定在另一棵树，再次找重心
7.对两个重心连边之后，dfs 维护 \(sz\) 并枚举求答案
CF708C Centroids
好题。
- 方法 1：暴力
1.枚举每个点 \(i\) 作为根，维护最大子树大小 \(mxs_i\)
2.若 \(mxs_i > \frac{n}{2}\)，尝试在 \(i\) 的重儿子中 \(son_i\) 分离一颗不超过 \(\frac{n}{2}\) 的子树 \(part_{son_i}\)，分离后剩余 \(mxs_i - part_{son_i} \le \frac{n}{2}\)，则 \(i\) 可以为重心
时间复杂度 \(O(n ^ 2)\)。
- 方法 2：换根避免枚举 \(n\) 个点
1.\(mxs_i,son_i\) 容易维护，难点在于 \(part_i\) 的维护
2.维护 \(part1_i\) 表示点 \(i\) 最大的不超过 \(\frac{n}{2}\) 的子树大小，\(part2_i\) 表示次大
3.维护 \(up_i\) 表示点 \(i\) 子树外的最大的不超过 \(\frac{n}{2}\) 的子树大小
4.若 \(mxs_i > \frac{n}{2}\)，检查 \(mxs_i - part1_i \le \frac{n}{2}\)，若 \(n - sz_x > \frac{n}{2}\)，检查 \(n - sz_x - up_x \le \frac{n}{2}\)
树的中心
定义
当选取树上节点 \(x\)，为根时，最长链最短的点。
性质
- 树的中心至多有两个，且一定相邻（反证法）
- 树的中心一定在树的直径上，且为直径的中点
- 树的直径若有多条那么一定交于树的中心或两个树的中心的连边
- 树的中心为根时根到树的直径的两个端点就是最长链和次长链
求法
原理
求出树上每个点 \(i\) 的最长链。
步骤
1.维护 \(len1_i\) 表示以 \(i\) 为根的子树的最长链，维护 \(len2_i\) 表示以 \(i\) 为根的子树次长链，像树的直径一样维护即可
2.维护 \(up_i\) 表示点 \(i\) 在子树外的最长链，则：
\[up_u = up_x + w \\ up_u = \max \left \{ up_u, len1_x + w \right \} (len1_x + w \not = len1_x) \\ up_u = \max \left \{ up_u, len2_x + w \right \}(otherwise) \]3.\(\max \left \{ len1_x, up_x \right \}\) 最小的点即为树的中心
例题
U392706 【模板】树的中心
板子。