[JOI 2023 Final] Cat Exercise 题解

根据题意，设开始时猫在最高点 $u$ 上。当在 $u$ 放了一个障碍之后，则猫会跑次高点上。容易发现，当猫进入 $u$ 的其中一个子树后，就无法返回到 $u$ 的其他子树了，因为 $u$ 被堵上了。

那么，给猫留下一条活路之后，猫的行走路线就一定是固定的了。那么，只需要找到子树中能移动次数最多的子树，然后让猫过去即可。

尝试使用 $\text{DP}$ 进行求解。设 $dp_{u}$ 为以 $u$ 为根的子树中，猫从 $u$ 点出发可以走的最长距离。令 $u$ 的子树中最高的节点为 $pos_u$，$v$ 为 $u$ 的子节点，则 $dp_{u} = \max\{dp_{pos_{v}} + \operatorname{dist(u, v)}\}$。

接下来考虑如何实现。由于猫行走到的节点的高度呈单调递减，则必须先转移较小的 $v$，才能对较大的 $u$ 进行转移。那么我们可以考虑在连边时连接 $p_u$ 和 $p_v$，这样我们从 $1$ 至 $n$ 对每一个节点进行转移，就一定可以满足条件 $p_u > p_{pos_v}$。对于 $pos_v$ 我们可以用并查集来维护，对于 $\operatorname{dist}$ 函数，我们使用 $\text{lca}$ 进行求解即可。

Code

#include <iostream>
using namespace std;
typedef long long ll;
const ll mlg = 20, mxn = 2e5;
const ll lgN = mlg + 10, N = mxn + 10;
ll n, f[N], p[N], dp[N], head[N], cnt, fa[N][lgN], dep[N];
struct Edge { ll nxt, to; } e[N << 1];
void add(ll u, ll v) { e[++ cnt] = {head[u], v}; head[u] = cnt; }
ll rd() {
	ll sum = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
	return f ? -sum : sum;
}
void dfs(ll u, ll pre) {
	dep[u] = dep[pre] + 1, fa[u][0] = pre;
	for (ll i = 1; i <= mlg; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (ll i = head[u], v; i; i = e[i].nxt) {
		v = e[i].to;
		if (v == pre) continue;
		dfs(v, u);
	}
}
ll lca(ll u, ll v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (ll i = mlg; ~ i; -- i)
		if (dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if (u == v) return u;
	for (ll i = 20; ~ i; -- i)
		if (fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}//lca
ll get_fa(ll x) { return x == f[x] ? x : f[x] = get_fa(f[x]); }//并查集
ll dis(ll u, ll v) { return dep[u] + dep[v] - (dep[lca(u, v)] << 1); }//求距离
signed main() {
	n = rd();
	for (ll i = 1; i <= n; ++ i) f[i] = i, p[i] = rd();
	for (ll i = 1, u, v; i < n; ++ i) u = p[rd()], v = p[rd()], add(u, v), add(v, u);
	dfs(1, 0);
	for (ll u = 1; u <= n; ++ u)
		for (ll i = head[u], v; i; i = e[i].nxt) {
			v = get_fa(e[i].to);
			if (v < u) f[v] = u, dp[u] = max(dp[u], dp[v] + dis(u, v));
		}//如上文所述
	printf("%lld\n", dp[n]);
	return 0;
}