题解：P11294 [NOISG2022 Qualification] Tree Cutting
xiezheyuan
·
·
题解
感觉大家好像都写的是 O(n) 或 O(n\log n) 的，给大家来一个 O(n\log^2 n) 的做法养养眼（bushi），成功抢下最劣解。
简要题意
给定一个 n 个点的树，你需要断掉一条边并连接一条边，使得得到的无向图仍然构成一个树，在此基础上，最大化直径长度。输出这个最大长度。
Note：题意中没有显示要求剩下的图仍然是一棵树，但是如果不是一棵树的话“任意两城市之间的最远距离”是未定义的。
## 思路
我们考虑枚举断掉哪一条边，为了方便，我们随便钦定一个点为根，然后枚举这条边的两端点中深度较大的点。
现在的问题是接下来连哪条边更优，我们断掉这条边后实际上将原树分成了两个连通块，那么我们显然连接两个连通块的直径最优。答案就是这两个直径的长度之和加上 $1$（$1$ 表示连接的这条边的长度）。
于是我们转换成求每一个子树内 / 外的直径长度，比较好的做法是树形 dp，但是更加一般的做法是对树求一遍 dfs 序，则子树内的点位于连续区间内，用线段树维护区间直径即可。
用重链剖分求 LCA（用于求树上距离），时间复杂度 $O(n\log^2 n)$，实现精细的话换成欧拉序或 dfs 序求 LCA 可以做到 $O(n\log n)$。
## 代码
```cpp
#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 3e5 + 5;
int n;
vector<int> g[N];
int top[N], dep[N], siz[N], son[N], father[N], dfn[N], rev[N];
void dfs1(int u, int fa){
dep[u] = dep[fa] + 1, father[u] = fa, siz[u] = 1;
dfn[u] = ++dfn[0], rev[dfn[u]] = u;
for(int v : g[u]){
if(v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int fa){
if(son[u]){
top[son[u]] = top[u];
dfs2(son[u], u);
}
for(int v : g[u]){
if(v == fa || v == son[u]) continue;
top[v] = v;
dfs2(v, u);
}
}
int lca(int x, int y){
while(top[x] != top[y]){
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = father[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int dis(int x, int y){
return dep[x] + dep[y] - (dep[lca(x, y)] << 1);
}
struct node{
int x, y, len;
} t[N << 2];
node merge(node x, node y){
vector<node> kcr = {
{x.x, y.x, dis(x.x, y.x)}, {x.x, y.y, dis(x.x, y.y)},
{x.y, y.x, dis(x.y, y.x)}, {x.y, y.y, dis(x.y, y.y)},
x, y
};
return *max_element(kcr.begin(), kcr.end(), [](node x, node y){
return x.len < y.len;
});
}
void build(int i, int l, int r){
if(l == r) return (t[i] = {rev[l], rev[l], 0}), void();
build(ls, l, mid), build(rs, mid + 1, r);
t[i] = merge(t[ls], t[rs]);
}
node query(int ql, int qr, int i, int l, int r){
if(ql <= l && r <= qr) return t[i];
if(ql <= mid && qr > mid) return merge(query(ql, qr, ls, l, mid), query(ql, qr, rs, mid + 1, r));
else if(ql <= mid) return query(ql, qr, ls, l, mid);
return query(ql, qr, rs, mid + 1, r);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for(int i=1,u,v;i<n;i++){
cin >> u >> v;
g[u].emplace_back(v), g[v].emplace_back(u);
}
dfs1(1, 0), dfs2(1, 0), build(1, 1, n);
int ans = 0;
for(int i=2;i<=n;i++){
int in_tree = query(dfn[i], dfn[i] + siz[i] - 1, 1, 1, n).len;
int out_tree;
if(dfn[i] != 1 && dfn[i] + siz[i] <= n) out_tree = merge(query(1, dfn[i] - 1, 1, 1, n), query(dfn[i] + siz[i], n, 1, 1, n)).len;
else if(dfn[i] != 1) out_tree = query(1, dfn[i] - 1, 1, 1, n).len;
else out_tree = query(dfn[i] + siz[i], n, 1, 1, n).len;
ans = max(ans, in_tree + out_tree);
}
cout << ans + 1;
return 0;
}
// Written by xiezheyuan
```