• Update on 2022.11.25 重写题解，原题解见 链接。

P3596 [POI2015] MOD

考虑枚举断掉的边，我们希望快速求出形成的两个连通块的直径 $d_1$ 和 $d_2$，则连一条边形成的直径最大长度为 $d_1 + d_2 + 1$（连接两连通块直径一段），最小直径长度为 $\max(d_1, d_2, \lceil \frac {d_1} 2 \rceil + \lceil \frac {d_2} 2\rceil + 1)$（连接两连通块直径中点）。

设 $f_i$ 表示子树最长竖直链，$g_i$ 表示子树直径，则

$$\begin{aligned} f_i & = \max\limits_{u \in \mathrm{son}(i)} f_u + 1 \\ g_i & = \max\left(\max_{u\in \mathrm{son}(i)} g_u, \max_{u, v\in \mathrm{son}(i), u\neq v} f_u + f_v + 2\right) \end{aligned}$$

求每棵子树的直径可直接换根 DP。换根 DP 过程中需要对 $i$ 求出将每个儿子 $u$ 从 $\mathrm{son}(i)$ 中删除后新的 $f$ 和 $g$ 值，使用维护前后缀的经典套路，$f$ 容易维护，$g$ 在合并的时候还需要和前缀 $\max f$ 与后缀 $\max f$ 之和取 $\max$。

时间复杂度 $\mathcal{O}(n)$。因需构造方案，所以需要维护最长竖直链的一段和直径两端，使用结构体可避免繁琐的分类讨论。

#include <bits/stdc++.h>
using namespace std;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC

constexpr int N = 5e5 + 5;
vector<int> e[N];
int n;
struct chain {
  int u, d;
  chain operator + (const int &z) const {return {u, d + z};}
  bool operator < (const chain &z) const {return d < z.d;}
} f[N], ff[N];
struct diam {
  int u, v, d;
  void print() {cout << "diameter: u = " << u << ", v = " << v << ", d = " << d << "\n";}
  diam operator + (const int &z) const {return {u, v, d + z};}
  bool operator < (const diam &z) const {return d < z.d;}
} g[N], gg[N];
diam operator + (const chain &x, const chain &y) {return {x.u, y.u, x.d + y.d};}

void dfs1(int id, int fa) {
  f[id] = {id, 0}, g[id] = {id, id, 0};
  for(int it : e[id]) {
    if(it == fa) continue;
    dfs1(it, id);
    g[id] = max(g[id], max(g[it], f[id] + f[it] + 1));
    f[id] = max(f[id], f[it] + 1);
  }
}

int mxd, mxeu, mxev;
int mnd = N, mneu, mnev;
diam mxu, mxv, mnu, mnv;
void dfs2(int id, int fa) {
  if(fa) {
    // cout << "dfs2 " << id << " " << fa << "\n";
    // g[id].print(), g[fa].print();
    int dist = g[id].d + g[fa].d + 1;
    if(dist > mxd) mxd = dist, mxu = g[id], mxv = g[fa], mxeu = id, mxev = fa;
    dist = max((g[id].d + 1 >> 1) + (g[fa].d + 1 >> 1) + 1, max(g[id].d, g[fa].d));
    if(dist < mnd) mnd = dist, mnu = g[id], mnv = g[fa], mneu = id, mnev = fa;
  }
  static chain fp[N], fs[N];
  static diam gp[N], gs[N];
  int sz = e[id].size();
  fp[0] = fs[sz + 1] = {id, 0};
  gp[0] = gs[sz + 1] = {id, id, 0};
  for(int i = 1; i <= sz; i++) {
    int it = e[id][i - 1];
    gp[i] = max(gp[i - 1], max(g[it], fp[i - 1] + f[it] + 1));
    fp[i] = max(fp[i - 1], f[it] + 1);
  }
  for(int i = sz; i; i--) {
    int it = e[id][i - 1];
    gs[i] = max(gs[i + 1], max(g[it], fs[i + 1] + f[it] + 1));
    fs[i] = max(fs[i + 1], f[it] + 1);
  }
  for(int i = 1; i <= sz; i++) {
    int it = e[id][i - 1];
    ff[it] = max(fp[i - 1], fs[i + 1]);
    gg[it] = max(max(gp[i - 1], gs[i + 1]), fp[i - 1] + fs[i + 1]);
  }
  for(int it : e[id]) if(it != fa) f[id] = ff[it], g[id] = gg[it], dfs2(it, id);
}

vector<int> pu, pv;
bool search(int id, int ff, int aim, vector<int> &arr) {
  arr.push_back(id);
  if(id == aim) return 1;
  for(int it : e[id]) if(it != ff && search(it, id, aim, arr)) return 1;
  arr.pop_back();
  return 0;
}

int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v), e[v].push_back(u);
  }
  dfs1(1, 0), dfs2(1, 0);
  cout << mnd << " " << mneu << " " << mnev << " ";
  search(mnu.u, 0, mnu.v, pu), search(mnv.u, 0, mnv.v, pv);
  cout << pu[mnu.d >> 1] << " " << pv[mnv.d >> 1] << "\n";
  cout << mxd << " " << mxeu << " " << mxev << " " << mxu.v << " " << mxv.u << "\n";
  return cerr << "Time: " << TIME << " ms\n", 0;
}

翻了一遍题解区发现 SDNetFriend 的做法非常巧妙。对于直径最小值，我们一定会断掉直径的一条边，所以只需以直径两端为根进行树形 DP。对于直径最大值，若断掉非直径上的边，则不包含直径的子树在直径两端 DP 时也已经求出，而包含直径的子树的直径即原树直径，以此避免较繁琐的换根 DP。