P9487 「LAOI-1」小熊游景点 题解
5k_sync_closer
·
·
题解
出题人题解。
设 x(u,v) 为 u\to v 路径边权和，y(u,v) 为 u\to v 路径点权和。
题目中求 x(a,p)+x(b,p)+2x(p,q)=x(a,b)+2x(p,q) 最小的前提下 y(a,p)+y(b,p)+2y(p,q)-2s_p=y(a,b)+2y(p,q)-s_p 最大，
考虑对每个 $a\to b$ 路径上的 $p$ 维护出 $x(p,q)$ 最小值以及此时 $2y(p,q)-s_p$ 最大值。
用**换根 DP** 维护之。设 $f_{p,0/1}$ 为 $q$ 在 $x$ 子树内时 $x(p,q)$ 的最小值 / 次小值，则容易得到状态转移方程：
$$
\begin{aligned}
f_{p,0}&=\min(\{f_{q,0}+x(p,q)|q\in son_p\}\cup\{0\})\\
f_{p,1}&=\mathop{\operatorname{secondmin}}(\{f_{q,0}+x(p,q)|q\in son_p\}\cup\{0\})
\end{aligned}
$$
转移时记录 $2y(p,q)-s_p$ 最大值。
设 $g_{p,0/1}$ 为 $x(p,q)$ 的最小值 / 次小值，则 $g_p$ 由 $f_p,g_{fa_p}$ 转移而来，$g_{fa_p}$ 由 $f_{fa_p},g_{fa_{fa_p}}$ 转移而来，$f_{fa_p}$ **可能**由 $f_p$ 转移而来，存在重复计算。
需要记录 $k_p$ 为转移到 $g_p$ 的点，从而消除重复计算。
则有状态转移方程：
$$
\begin{aligned}
g_{p,0}&=\min\{f_{p,0},g_{fa_p,[k_{fa_p}=p]}+x(p,fa_p)\}\\
g_{p,1}&=\mathop{\operatorname{secondmin}}\{f_{p,0},f_{p,1},g_{fa_p,[k_{fa_p}=p]}+x(p,fa_p)\}
\end{aligned}
$$
转移时记录 $2y(p,q)-s_p$ 最大值。
则问题转化为求静态树链最小值，用树上倍增维护之。
```cpp
#include <cstdio>
#include <algorithm>
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
using namespace std;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline int R()
{
int r = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9')
f = c == '-', c = getchar();
while (c >= '0' && c <= '9')
r = r * 10 + c - '0', c = getchar();
return f ? -r : r;
}
void P(long long x)
{
if (x < 0)
*O++ = '-', x = -x;
if (x >= 10)
P(x / 10);
*O++ = x % 10 + '0';
}
struct S
{
long long x, y, p;
S operator+(S b) { return {x + b.x, y + b.y}; }
bool operator<(S b) const { return x == b.x ? y > b.y : x < b.x; }
} Q, F[300050][2], C[300050][20];
struct E
{
int v, w, t;
} e[1000050];
int n, m, c, a[300050], d[300050], h[300050], f[300050][20];
long long s[300050];
void A(int u, int v, int w)
{
e[++c] = {v, w, h[u]};
h[u] = c;
}
void D1(int u)
{
for (int i = h[u], v; i; i = e[i].t)
if (!d[v = e[i].v])
{
d[v] = d[u] + 1;
f[v][0] = u;
for (int i = 1; f[v][i - 1]; ++i)
f[v][i] = f[f[v][i - 1]][i - 1];
s[v] = s[u] + a[v];
D1(v);
S X = F[v][0] + S{e[i].w, a[v] << 1};
X.p = v;
if (X < F[u][0])
F[u][1] = F[u][0], F[u][0] = X;
else if (X < F[u][1])
F[u][1] = X;
}
}
void D2(int u, int k)
{
for (int i = h[u], v; i; i = e[i].t)
if ((v = e[i].v) != k)
{
S X = F[u][F[u][0].p == v] + S{e[i].w, a[u] << 1};
X.p = u;
if (X < F[v][0])
F[v][1] = F[v][0], F[v][0] = X;
else if (X < F[v][1])
F[v][1] = X;
D2(v, u);
}
}
void D3(int u, int k)
{
for (int i = h[u], v; i; i = e[i].t)
if ((v = e[i].v) != k)
{
C[v][0] = F[v][0];
for (int i = 1; f[v][i - 1]; ++i)
C[v][i] = min(C[v][i - 1], C[f[v][i - 1]][i - 1]);
D3(v, u);
}
}
int main()
{
n = R();
m = R();
for (int i = 1; i <= n; ++i)
a[F[i][0].p = F[i][1].p = i] = R();
for (int i = 1, u, v, w; i < n; ++i)
u = R(), v = R(), A(u, v, w = R()), A(v, u, w);
s[1] = a[1];
D1(d[1] = 1);
D2(1, 0);
for (int i = 1; i <= n; ++i)
F[i][0].y += a[i], F[i][1].y += a[i];
C[1][0] = F[1][0];
D3(1, 0);
for (int i = 0, x, y, u, v, l, k; i < m; ++i)
{
Q = {1000000000000000000ll, 0};
if (d[u = x = R()] < d[v = y = R()])
swap(x, y);
while (d[x] > d[y])
Q = min(Q, C[x][k = __lg(d[x] - d[y])]), x = f[x][k];
if (x == y)
Q = min(Q, C[l = x][0]);
else
{
for (k = __lg(d[x]); k >= 0; --k)
if (f[x][k] != f[y][k])
Q = min({Q, C[x][k], C[y][k]}), x = f[x][k], y = f[y][k];
Q = min({Q, C[x][0], C[y][0], C[l = f[x][0]][0]});
}
P(Q.y + s[u] + s[v] - s[l] - s[f[l][0]]);
*O++ = '\n';
}
fwrite(obuf, O - obuf, 1, stdout);
return 0;
}
```