对链公共部分的形态分类讨论。
在讨论之前，先求出每条路径 在树上的 LCA 结点 。
1. 链公共部分是一条直链
枚举直链深度最大的点为 ，则对第 条路径 而言，若其有恰好一个端点在 结点为根的子树中，则其在 位置往上最多能覆盖到 位置。
而若第 条路径和第 条路径都存在恰好一个端点在 结点为根的子树中，则 结点一定在这两条路径的公共部分中，其从 位置开始向上的公共路径长度就是 。
固定 时 是定值，为了让答案最大只需要让 的值最大也就是 的值最小，因此只需要对每个 点都求出恰好有一个端点在 子树内的路径中 最小的两条即可。
然后发现这个东西可以直接树上 dp 求出来，维护 表示 点子树内 最小的两条路径的 值， 是对应 的路径编号，则转移可以考虑提前维护集合 表示所有满足存在一个端点为 的路径组成的编号集合，然后初始化的时候直接把 集合内所有路径的答案更新到 和 上，然后直接DFS 整个树更新 dp 信息即可。
2. 链公共部分存在拐点
此时两条路径 必然满足其 LCA 对应点相同即 ，因此容易想到维护集合 表示所有满足 LCA 为 的路径组成的编号集合。
考虑枚举这个链的一个单链最深点 ，这里认为路径端点中 点在 为根的子树中， 点不在 为根的子树中。
若链的另一个单链最深点为 ，则这个链的长度就是 。因为 和链的 LCA 结点 都已经确定了，因此贪心的希望 点的深度最大。
于是问题被转化为：
枚举点 ，在所有满足一侧端点 LCA 为 的路径对 中，找出一对满足 且另一侧端点 LCA 尽量深的点对。
在 的子树中选两个点 使得其 LCA 为 ，只需要满足 不同时在 的某个儿子结点为根的子树中即可。
然后现在问题是找另一个单链最深点 。有经典结论是 LCA 深度最深的点一定是所有候选点按照 DFS 序排序后在相邻点对中选出。因此可以在 DFS 过程中用 multiset 来维护当前的候选集合，这样每在候选集合中添加一个点时只需要和其关于 DFS 序的前驱 / 后继结点求 LCA 并更新答案即可。
合并子树的 multiset 信息可以套路的启发式合并。
因此问题被解决，总时间复杂度为 ，可以通过该题。
:::success[代码实现]
namespace lowspeed_song {
inline void init() {
}
vector<int> adj[N], A[N];
int n, k, u[N], v[N], w[N], timestamp, f[20][N], dfn[N], dep[N], lg[N];
inline int get(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline void dfs(int u, int fa) {
dep[u] = dep[fa] + 1, f[0][dfn[u] = ++timestamp] = fa;
for (int &v : adj[u]) if (v != fa) dfs(v, u);
}
inline int lca(int u, int v) {
if (u == v) return u;
u = dfn[u], v = dfn[v];
if (u > v) swap(u, v);
int lgx = lg[v - u++];
return get(f[lgx][u], f[lgx][v - (1 << lgx) + 1]);
}
inline int dist(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int mx = -1, AA, BB;
inline void chkmax(int val, int u, int v) {
if (val > mx) mx = val, AA = u, BB = v;
}
namespace Sub1 {
int f[N][2], g[N][2];
inline void upd(int x, int d, int id) {
if (!id) return;
if (g[x][0] == id) { f[x][0] = min(f[x][0], d); return; }
if (g[x][1] == id) {
f[x][1] = min(f[x][1], d);
if (f[x][1] < f[x][0]) swap(f[x][0], f[x][1]), swap(g[x][0], g[x][1]);
return;
}
if (d < f[x][0]) {
f[x][1] = f[x][0], g[x][1] = g[x][0];
f[x][0] = d, g[x][0] = id;
} else if (d < f[x][1]) f[x][1] = d, g[x][1] = id;
}
inline void dfs(int u) {
f[u][0] = f[u][1] = inf, g[u][0] = g[u][1] = 0;
for (int &v : A[u]) upd(u, dep[w[v]], v);
for (int &v : adj[u]) dfs(v), upd(u, f[v][0], g[v][0]), upd(u, f[v][1], g[v][1]);
if (g[u][0] && g[u][1]) chkmax(dep[u] - max(f[u][0], f[u][1]), g[u][0], g[u][1]);
}
}
namespace Sub2 {
struct Info { int x, id; };
inline int oth(const Info &r) { return u[r.id] == r.x ? v[r.id] : u[r.id]; }
struct Cmp {
inline bool operator()(const Info &l, const Info &r) const {
int a = oth(l), b = oth(r);
if (dfn[a] != dfn[b]) return dfn[a] < dfn[b];
return l.id < r.id || l.id == r.id && l.x < r.x;
}
};
multiset<Info, Cmp> se[N];
inline void chk(int u, Info a, Info b) {
if (a.id == b.id || w[a.id] != w[b.id]) return;
if (dep[u] < dep[w[a.id]]) return;
int x = oth(a), y = oth(b), w = lca(x, y), v = dist(w, u);
chkmax(v, a.id, b.id);
}
inline void ins(int u, Info x) {
auto it = se[u].lower_bound(x);
if (it != se[u].end()) chk(u, x, *it);
if (it != se[u].begin()) chk(u, x, *prev(it));
se[u].emplace(x);
}
inline void dfs(int u) {
for (int &v : A[u]) ins(u, Info{u, v});
for (int &v : adj[u]) {
dfs(v);
if (se[u].size() < se[v].size()) se[u].swap(se[v]);
for (const Info &i : se[v]) ins(u, i);
multiset<Info, Cmp>().swap(se[v]);
}
}
}
inline void sol() {
cin >> n >> k;
for (int i = 2; i <= n; ++i) {
int x; cin >> x;
adj[x].emplace_back(i);
}
lg[0] = -1;
for (int i = 1; i < N; ++i) lg[i] = lg[i >> 1] + 1;
dfs(1, 0);
for (int i = 1; i < 20; ++i)
for (int j = 1; j + (1 << i) - 1 <= n; ++j)
f[i][j] = get(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
for (int i = 1; i <= k; ++i) {
cin >> u[i] >> v[i];
w[i] = lca(u[i], v[i]);
A[u[i]].emplace_back(i);
A[v[i]].emplace_back(i);
}
Sub1::dfs(1), Sub2::dfs(1);
if (mx <= 0) mx = 0, AA = 1, BB = 2;
cout << mx << '\n' << AA << ' ' << BB << '\n';
}
} // namespace lowspeed_song
喜欢的话，留下你的评论吧～