自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:06:10，当前版本为作者最后更新于2024-11-21 19:42:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉大家好像都写的是 $O(n)$ 或 $O(n\log n)$ 的，给大家来一个 $O(n\log^2 n)$ 的做法养养眼（bushi），成功抢下最劣解。

简要题意

给定一个 $n$ 个点的树，你需要断掉一条边并连接一条边，使得得到的无向图仍然构成一个树，在此基础上，最大化直径长度。输出这个最大长度。

$1\leq n\leq 3\times 10^5$。

Note：题意中没有显示要求剩下的图仍然是一棵树，但是如果不是一棵树的话“任意两城市之间的最远距离”是未定义的。

思路

我们考虑枚举断掉哪一条边，为了方便，我们随便钦定一个点为根，然后枚举这条边的两端点中深度较大的点。

现在的问题是接下来连哪条边更优，我们断掉这条边后实际上将原树分成了两个连通块，那么我们显然连接两个连通块的直径最优。答案就是这两个直径的长度之和加上 $1$（$1$ 表示连接的这条边的长度）。

于是我们转换成求每一个子树内 / 外的直径长度，比较好的做法是树形 dp，但是更加一般的做法是对树求一遍 dfs 序，则子树内的点位于连续区间内，用线段树维护区间直径即可。

用重链剖分求 LCA（用于求树上距离），时间复杂度 $O(n\log^2 n)$，实现精细的话换成欧拉序或 dfs 序求 LCA 可以做到 $O(n\log n)$。

代码

#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