题目描述
Brain Network (hard) 这个问题就是给出一个不断加边的树，保证每一次加边之后都只有一个连通块（每一次连的点都是之前出现过的），问每一次加边之后树的直径。
算法
每一次增加一条边之后，树的直径长度要么不变，要么会增加1，并且如果树的直径长度增加1了，新的直径的端点其中一个必然是新增的点，而另一个是原来直径的某个端点。关于为什么可以这样做，在Quora上有个回答解释地不错，可以参考。
实现
所以这个问题其实就是要计算树上任意两个点的距离，LCA可以很轻松地处理。
可以一次性先把数据都读完，建树，因为每一次询问，后面加入的边不会对当前询问造成影响。
如果用二进制祖先那种搞法来算LCA的话，也可以每读一个新增点就去算一下，相当于是把原来的过程给拆开了。
下面是我的代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>using namespace std;const int N = 223456;struct Edge {
int to, next;
} edge[N << 1];
int idx = 1, head[N];void addEdge(int u, int v) {
edge[++idx].to = v;
edge[idx].next = head[u];
head[u] = idx;
}void init() {
memset(head, 0, sizeof(head));
idx = 1;
}int par[N][21];
int dep[N];void dfs(int u, int fa, int d) {
dep[u] = d;
for (int k = head[u]; k; k = edge[k].next) {
int v = edge[k].to;
if (v == fa) continue;
par[v][0] = u;
dfs(v, u, d + 1);
}
}void calc(int n) {
for (int i = 1; i <= 20; i++) {
for (int j = 1; j <= n; j++) {
par[j][i] = par[par[j][i - 1]][i - 1];
}
}
}int kthA(int u, int k) {
for (int i = 20; i >= 0; i--) {
if (k >= (1 << i)) {
k -= (1 << i);
u = par[u][i];
}
}
return u;
}int lca(int u, int v) {
if (dep[u] < dep[v])swap(u, v);
u = kthA(u, dep[u] - dep[v]);
if (u == v)return u;
for (int i = 20; i >= 0; i--) {
if (par[u][i] == par[v][i])continue;
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}bool update(int u, int v, int &k) {
int a = lca(u, v);
int d = dep[u] + dep[v] - 2 * dep[a];
if (d > k) {
k = d;
return true;
}
return false;
}int a[N];int main() {
int n;
scanf("%d", &n);
int u = 1, v = 1, cur = 0;
init();
for (int i = 2; i <= n; i++) {
scanf("%d", a + i);
addEdge(a[i], i);
}
dfs(1, -1, 0);
calc(n);
for (int i = 2; i <= n; i++) {
int nv = v;
if (update(u, i, cur)) {
nv = i;
}
if (update(v, i, cur)) {
u = v;
nv = i;
}
v = nv;
printf("%d ", cur);
}
puts("");
return 0;
}
