两人的行走可以分成两类：
①在两人的路径上；
②离开这条路径后一直走到叶子节点；
那么我们可以先把这条路径上每个点到 除了包含这条路径 的叶子 的最长路径，假设A和B两个人的距离是x，这样就得到了一个长度为x的上述数组。
之后就去模拟每个人选取最优的行动：
int solve(int l, int r, int flag)//l为A所在位置，r为B所在位置，flag判断当前回合谁走
{
if (l == r - 1)
return a[r] - b[l];
//每次都min(从当前点离开两人的最简路径，继续往前走)中取最优策略
if (!flag)
return min(solve(l + 1, r, (flag ^ 1)), query(l + 1, r, 1, 1) - b[l]);//B的策略是让B-A最大（即A-B最小）
else
return max(solve(l, r - 1, (flag ^ 1)), a[r] - query(l, r - 1, 1, 2));//A的策略是A-B的差值最大
}
每一步取最值用任意数据结构优化到log即可，总复杂度nlogn
#include<bits/stdc++.h>
//#include<unordered_map>
using namespace std;
#define ll long long
//#define double long double
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pii pair<int,int>
#define pll pair<ll,ll>
const double PI = acos(-1);
const int inf = 1e9;
const ll lnf = 1e18 + 7;
const int maxn = 1e6 + 10;
const int N = 1 << 30 - 1;
ll mod = 998244353;
double eps = 1e-8;
int n, S, T;
int cnt = 0, head[maxn];
struct edge {
int to, next;
}e[maxn << 1];
inline void add(int from, int to)
{
e[++cnt] = { to,head[from] };
head[from] = cnt;
}
int deep[maxn], fa[maxn], dm[maxn];
void dfs(int from)//预处理深度
{
dm[from] = deep[from];
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to;
if (to == fa[from])continue;
deep[to] = deep[from] + 1;
fa[to] = from;
dfs(to);
dm[from] = max(dm[from], dm[to]);
}
}
int a[maxn], b[maxn];//从两个方向走的最大长度
struct tree {
int l;
int r;
int MAX1, MAX2;//维护a和b两个数组的最值
}t[4 * maxn];
void build(int l, int r, int p)
{
t[p].l = l;
t[p].r = r;
t[p].MAX1 = -inf;
t[p].MAX2 = -inf;
if (l == r) { t[p].MAX1 = a[l]; t[p].MAX2 = b[l]; return; }
int mid = l + r >> 1;
build(l, mid, p << 1);
build(mid + 1, r, p << 1 | 1);
t[p].MAX1 = max(t[p << 1].MAX1, t[p << 1 | 1].MAX1);
t[p].MAX2 = max(t[p << 1].MAX2, t[p << 1 | 1].MAX2);
}
int query(int x, int y, int p, int flag)
{
if (x > y)return -inf;
int l = t[p].l;
int r = t[p].r;
if (l >= x && r <= y)
{
return (flag == 1 ? t[p].MAX1 : t[p].MAX2);
}
int mid = l + r >> 1;
if (y <= mid)return query(x, y, p << 1, flag);
else if (x > mid)return query(x, y, p << 1 | 1, flag);
else
return max(query(x, y, p << 1 | 1, flag), query(x, y, p << 1, flag));
}
int solve(int l, int r, int flag)
{
if (l == r - 1)
return a[r] - b[l];
if (!flag)
return min(solve(l + 1, r, (flag ^ 1)), query(l + 1, r, 1, 1) - b[l]);
else
return max(solve(l, r - 1, (flag ^ 1)), a[r] - query(l, r - 1, 1, 2));
}
int main()
{
//freopen("C:\Users\Administrator\Documents\Tencent Files\1320265781\FileRecv\2021牛客多校第八场数据\J-Tree\15.in", "r", stdin);
/*
3 1 3
1 2
2 3
*/
fastio;
memset(head, -1, sizeof(head));
cnt = 0;
cin >> n >> S >> T;
for (int i = 1; i < n; i++)
{
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
deep[S] = 0;
dfs(S);
int cnt = 0, last = T;
for (int now = T;; now = fa[now])
{
a[++cnt] = deep[now] + 1;
b[cnt] = deep[T] - deep[now] + 1;
dm[now] = 0;
for (int i = head[now]; ~i; i = e[i].next)
{
int to = e[i].to;
if (to == last || to == fa[now])continue;
a[cnt] = max(a[cnt], dm[to] + 1);
b[cnt] = max(b[cnt], dm[to] - deep[now] + deep[T] - deep[now] + 1);
dm[now] = max(dm[now], dm[to]);
}
last = now;
if (now == S)break;
}
build(1, cnt, 1);
cout << solve(1, cnt, 1) << endl;
return 0;
}