AcWing 5560. 树的直径
原题链接
困难
树的直径:从树中任一点 A 通过 dfs 或者 bfs 找到距离 A 最远的点 B 再从 B 做一遍 dfs 或者 bfs 找到距离 B 最远的点 C 则 B - C 这条路径为该树的一条直径 B 和 C 为这条直径的两个端点
现假设当前树的直径为 A - B 在树中任选一叶子结点
假设为 C 增加的两个节点设为 x 和 y 若树的直径会变的更长
则只有可能为四种情况 分别为 A - x 和 B - x 和 A - y 和 B - y 由于 x 和 y 对称 所以只有两种情况 即 A - x 和 B - x
证明:原树中的直径为 A - B 则 A 或 B 到原树其他点的距离一定小于等于 A - B 这段距离 若直径变大 则只可能是 A - x 或者 B - x 大于 A - B
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10; // 初始 4 个点 每次操作加 2 个点 最多进行 5 * 10 ^ 5 次操作 所以最多 1e6 + 4 个点
int q;
int n = 4; // 表示当前树中的点数
int fa[N][20]; // 2 ^ 20 - 1 > 1e6 + 10
int depth[N]; // 存储每个点的层数
int d[N]; // 存储每个点到根节点的距离
int lca(int a, int b) { // 返回树中两点 a 和 b 的最近公共祖先
if (depth[a] < depth[b]) swap(a, b);
// 将 a 跳到与 b 同一层
for (int k = 19; k >= 0; k--)
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
// 如果 a == b 则说明 b 就是 a 和 b 的最近公共祖先
if (a == b) return b;
// a != b 则将 a 和 b 一起向上跳到其最近公共祖先的下一层
for (int k = 19; k >= 0; k--)
if (fa[a][k] != fa[b][k])
a = fa[a][k], b = fa[b][k];
// a 或 b 再向上跳 1 = 2 ^ 0 步得到的点就是 a 和 b 的最近公共祖先
return fa[a][0];
}
int get_dist(int a, int b) { // 计算树中两点 a 和 b 的距离
return d[a] + d[b] - 2 * d[lca(a, b)]; // 公式:d[a] + d[b] - 2 * d[lca(a, b)]
}
int main() {
scanf("%d", &q);
// 初始化depth[]
depth[0] = 0; // 哨兵
depth[1] = 1; // 根节点层数为 1
for (int i = 2; i <= 4; i++) depth[i] = 2;
// 初始化d[]
depth[1] = 0; // 根到根的距离为 0
for (int i = 2; i <= 4; i++) d[i] = 1; // 2,3,4号节点为根节点的叶子节点 所以到根距离为 1
// A 和 B 记录当前树的直径的两个端点 res 记录当前树的直径
int A = 2, B = 3, res = 2; // 设初始直径的两个端点为 2 和 3 长度为 2
while (q--) {
int id; scanf("%d", &id);
int x = ++n, y = ++n; // 新加的两个点的编号
depth[x] = depth[y] = depth[id] + 1; // 更新层数
d[x] = d[y] = d[id] + 1; // 更新到根的距离
fa[x][0] = id, fa[y][0] = id; // 向上跳 2 ^ 0 = 1 步的节点编号为 id
for (int k = 1; k <= 19; k++) {
fa[x][k] = fa[fa[x][k - 1]][k - 1];
fa[y][k] = fa[fa[y][k - 1]][k - 1];
}
// 更新 A 和 B 和 res
int dax = get_dist(A, x), dbx = get_dist(B, x);
if (dax > dbx && dax > res) res = dax, B = x;
else if (dbx >= dax && dbx > res) res = dbx, A = x;
printf("%d\n", res);
}
return 0;
}