题意:给定一棵树,初始时含有 4 个结点分别为 1 到 4,其中 1 号为根结点,2 到 4 均为根结点的叶子结点。现在进行 Q 次操作,每次指定一个已经存在的结点向其插入两个新结点作为叶节点。现在需要在每次操作以后输出这棵树的直径。我们定义树的直径为:树中距离最远的两个点之间的距离。
思路一:暴力搜索。我们将树重构为无向图,对于每一个状态的无向图,首先从任意一个已存在的结点 A 开始搜索到距离他最远的点 B,然后从 B 点出发搜索到离他最远的点 C,则 B 与 C 之间的距离就是当前状态的树的直径。由于每一个状态的树都要遍历两遍树,于是时间复杂度就是平方阶
时间复杂度:$O(qn)$
思路二:最近公共祖先 LCA。
从树的直径出发。我们知道,树的直径由直径的两个结点之间的距离决定,因此我们着眼于这两个结点 $A$ 和 $B$ 展开。不妨设当前局面直径的两个结点已知为 $A$ 和 $B$,现在插入两个叶子结点 $L_1$ 和 $L_2$。是否改变了树的直径大小取决于新插入的两个结点对于当前树的影响情况。如果 $L_1$ 或 $L_2$ 可以替代 $A$ 或 $B$,则树的直径就会改变。很显然新插入的两个叶子结点对于直径的两个端点影响是同效果的,因此我们统称新插入的叶子结点为 $L$。
什么时候树的直径会改变?对于 $A$、$B$ 和 $L$ 来说,直径是否改变取决于 $L$ 能否替代 $A$ 或 $B$,一共有六种情况。我们记 $\text{dist}(A,L)=da$,$\text{dist}(B,L)=db$,当前树的直径为 $res$,六种情况如下:
- $\text{max}(da, db) \le \text{res}$,交换 $A$ 和 $B$ 得到 $2$ 种
- $\text{min}(da,db) \ge \text{res}$,交换 $A$ 和 $B$ 得到 $2$ 种
- $\text{max}(da,db) >res,\text{min}(da,db) < \text{res}$,交换 $A$ 和 $B$ 得到 $2$ 种
如图:我们只需要在其中的最大值严格超过当前树的直径 $\text{res}$ 时更新直径对应的结点以及直径的长度即可
如何快速计算树上任意两个点之间的距离?我们可以使用最近公共祖先 LCA 算法。则树上任意两点 $x,y$ 之间的距离 $\text{dist}(x,y)$ 为:
$$ \text{dist}(x,y) = \text{dist}(x,root) + \text{dist}(y,root) - 2 \times \text{dist}(\text{lca}(x,y),root) $$时间复杂度:$O(q \log n)$
暴力搜索代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
const int N = 500010;
vector<int> g[N];
int d[N];
bool vis[N];
pair<int, int> res; // first 为最远距离;second 为对应结点编号
void dfs(int pre, int now) {
if (vis[now]) return;
vis[now] = true;
if (pre != -1) {
d[now] = d[pre] + 1;
if (d[now] > res.first) {
res = {d[now], now};
}
}
for (auto& ch: g[now]) {
dfs(now, ch);
}
}
void solve() {
// init
for (int i = 2; i <= 4; i++) {
g[1].push_back(i);
g[i].push_back(1);
}
int now = 4;
int Q;
cin >> Q;
while (Q--) {
int id;
cin >> id;
g[id].push_back(++now);
g[now].push_back(id);
g[id].push_back(++now);
g[now].push_back(id);
res = {-1, -1};
// 第一趟
memset(vis, false, sizeof vis);
memset(d, 0, sizeof d);
d[1] = 0;
dfs(-1, 1);
// 第二趟
memset(vis, false, sizeof vis);
memset(d, 0, sizeof d);
d[res.second] = 0;
dfs(-1, res.second);
cout << res.first << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}
LCA 代码
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <set>
using namespace std;
const int N = 1000010, M = 20;
int d[N]; // d[i] 表示 i 号点到根结点的距离
int to[N][M]; // to[i][j] 表示 i 号点向上跳 2^j 步后到达的结点编号
int lca(int a, int b) {
if (d[a] < d[b]) swap(a, b);
for (int k = M - 1; k >= 0; k--)
if (d[to[a][k]] >= d[b])
a = to[a][k];
if (a == b) return a;
for (int k = M - 1; k >= 0; k--)
if (to[a][k] != to[b][k])
a = to[a][k], b = to[b][k];
return to[a][0];
}
int dist(int a, int b) {
return d[a] + d[b] - 2 * d[lca(a, b)];
}
void solve() {
int Q;
cin >> Q;
// init lca
for (int i = 2; i <= 4; i++) {
d[i] = 1;
to[i][0] = 1;
}
int A = 2, B = 4, now = 4, res = 2;
while (Q--) {
int fa;
cin >> fa;
int L1 = ++now, L2 = ++now;
// upd lca
d[L1] = d[fa] + 1;
d[L2] = d[fa] + 1;
to[L1][0] = fa;
to[L2][0] = fa;
for (int k = 1; k <= M - 1; k++) {
to[L1][k] = to[ to[L1][k-1] ][ k-1 ];
to[L2][k] = to[ to[L2][k-1] ][ k-1 ];
}
int da = dist(A, L1), db = dist(B, L1);
if (max(da, db) <= res) res = res;
else if (min(da, db) >= res) {
if (da > db) res = da, B = L1;
else res = db, A = L1;
} else {
if (da > db) res = da, B = L1;
else res = db, A = L1;
}
cout << res << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}