闲话

把 T2 出得比 T1 简单，颇有 CSP-S 2022 复赛之遗风。

题解

考虑将答案拆分成两个部分。

第一个部分为无论如何选择 $z_i$ 都必然获得的利润，显然，这个值是两端点城市演讲收入之和减去两城市之间路费的值。

第二个部分为选择 $z_i$ 所获得的额外利润。额外利润的值是 $z_i$ 的演讲收入减去从 $z_i$ 走到两城市之间路径上所需的最少路费的 $2$ 倍。因为 $z_i$ 是第二个城市，所以需要从路径的某一个点开始走到 $z_i$ 再原路返回。

令 $d_{i,j}$ 为从城市 $i$ 到城市 $j$ 需要花费的最少路费，$d_{i,(u,v)}$ 为从城市 $i$ 走到路径 $(u,v)$ 上需花费的最少路费。显然，当 $i$ 在 $(u,v)$ 上时，$d_{i,(u,v)}=0$。

答案可表示为 $c_x+c_y-d_{x,y}+c_z-2d_{z,(x,y)}$。

答案的前三个量都可以通过树上前缀和轻松求得。考虑如何快速求最后两个量。

将最后两项捆绑起来求。

考虑对于每一个点 $x$ 求 $\max_{1\le i\le n}(c_i-2d_{x,i})$。

首先，可以按照树上广义后序遍历顺序求出 $\max_{i\in S_x}(c_i-2d_{x,i})$，其中 $S_x$ 为节点 $x$ 的子树内节点集合。令上述值为 $r_x$，则 $r_x\leftarrow\max_{i\in s_x}(r_i-2d_{x,i})$，其中 $s_x$ 为节点 $x$ 的儿子节点集合，请注意 $S_x$ 和 $s_x$ 的定义差别。

接下来，我们可以把子树信息和除了父节点以外的信息拼起来组成以每个节点为根的整棵树的答案，也就是按照树上广义前序遍历顺序求出 $\max_{1\le i\le n}(c_i-2d_{x,i})$，转移方法为 $r_x\leftarrow\max(r_x,r_{f_x}-2d_{x,f_x})$，其中 $f_x$ 为 $x$ 节点的父亲。特别的，不对遍历起点的节点进行此转移。

有了以上的信息后，使用树链剖分在每次询问时求解 $\max(c_z-2d_{z,(x,y)})$ 即可。

时间复杂度 $O(n\log^2 n)$。使用 ST 表进行实现可以做到 $O(n\log n)$，不过我并没有这样做。

注意：以下代码为赛时代码，没有严格使用上述方法对问题进行求解，可能会有部分不必要的复杂操作，请自行辨别并在 C+V 借鉴时加以改进。

#include <cctype>
#include <cstdio>
#include <set>
#include <utility>
#include <vector>
using namespace std;
const int N = 2e5 + 10;
int n, q, f[N], siz[N], ds[N], dfn[N], tp[N], idx, rnk[N], dep[N];
using ll = long long;
ll c[N], mx[N], dsv[N], fv[N];
using pil = pair<int, ll>;
vector<pil> road[N];
template <typename _Tp> inline void read(_Tp &x)
{
    static char ch;
    while (ch = getchar(), !isdigit(ch))
        ;
    x = (ch ^ 48);
    while (ch = getchar(), isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48);
}
template <typename _Tp, typename... _Args> inline void read(_Tp &x, _Args &...args)
{
    read(x);
    read(args...);
}
void dfs_init(int x)
{
    dep[x] = dep[f[x]] + 1;
    mx[x] = c[x];
    siz[x] = 1;
    for (auto &[i, v] : road[x])
    {
        if (i == f[x])
            continue;
        f[i] = x;
        fv[i] = v;
        dfs_init(i);
        siz[x] += siz[i];
        if (siz[i] > siz[ds[x]])
        {
            ds[x] = i;
            dsv[x] = v;
        }
        mx[x] = max(mx[x], mx[i] - v * 2);
    }
}
void dfs_build(int x, int ttp)
{
    dfn[x] = ++idx;
    rnk[idx] = x;
    tp[x] = ttp;
    if (!ds[x])
        return;
    mx[ds[x]] = max(mx[ds[x]], mx[x] - dsv[x] * 2);
    dfs_build(ds[x], ttp);
    for (auto &[i, v] : road[x])
    {
        if (i == f[x] or i == ds[x])
            continue;
        mx[i] = max(mx[i], mx[x] - v * 2);
        dfs_build(i, i);
    }
}
ll mxtr[N << 2], edv[N << 2];
void build(int x, int l, int r)
{
    if (l == r)
    {
        mxtr[x] = mx[rnk[l]];
        edv[x] = fv[rnk[l]];
        return;
    }
    int mid = (l + r) >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    edv[x] = edv[x << 1] + edv[x << 1 | 1];
    mxtr[x] = max(mxtr[x << 1], mxtr[x << 1 | 1]);
}
using pll = pair<ll, ll>;
pll query(int x, int l, int r, int lb, int rb)
{
    if (l >= lb and r <= rb)
        return {mxtr[x], edv[x]};
    pll res = {0, 0};
    int mid = (l + r) >> 1;
    if (lb <= mid)
    {
        auto [r1, r2] = query(x << 1, l, mid, lb, rb);
        res.first = max(res.first, r1);
        res.second += r2;
    }
    if (rb > mid)
    {
        auto [r1, r2] = query(x << 1 | 1, mid + 1, r, lb, rb);
        res.first = max(res.first, r1);
        res.second += r2;
    }
    return res;
}
pll query(int l, int r)
{
    pll res = {0, c[l] + c[r]};
    while (tp[l] != tp[r])
    {
        if (dep[tp[l]] > dep[tp[r]])
            swap(l, r);
        auto [r1, r2] = query(1, 1, n, dfn[tp[r]], dfn[r]);
        res.first = max(res.first, r1);
        res.second -= r2;
        r = f[tp[r]];
    }
    if (dep[l] > dep[r])
        swap(l, r);
    auto [r1, r2] = query(1, 1, n, dfn[l], dfn[r]);
    res.first = max(res.first, r1);
    res.second -= r2;
    res.second += fv[l];
    return res;
}
int main()
{
    // freopen("speaker.in", "r", stdin);
    // freopen("speaker.out", "w", stdout);
    read(n, q);
    for (int i = 1; i <= n; i++)
    {
        read(c[i]);
    }
    for (int i = 1, x, y, z; i < n; i++)
    {
        read(x, y, z);
        road[x].emplace_back(y, z);
        road[y].emplace_back(x, z);
    }
    dfs_init(1);
    dfs_build(1, 1);
    build(1, 1, n);
    // for (int i = 1; i <= n; i++)
    // {
    //     printf("%lld%c", mx[i], " \n"[i == n]);
    // }
    for (int i = 1, l, r; i <= q; i++)
    {
        read(l, r);
        auto [r1, r2] = query(l, r);
        printf("%lld\n", r1 + r2);
    }
}

Description

有一个 $n$ 个点的树，点 $i$ 有点权 $c_i$。边有边权。$q$ 次询问，每次询问给定两个点 $u,v$。再选一个点 $k$。最大化 $c_u+c_v+c_k-\operatorname{dis}_{u,k}-\operatorname{dis}_{k,v}$。

$n,q\le 2\times 10^5$。

Analysis

这种题一般考虑拆贡献。考虑我们实际要算什么。

$c_u+c_v$ 可以直接算。如果 $k$ 在 $u$ 到 $v$ 的路径上，$\operatorname{dis}_{u,k}+\operatorname{dis}_{k,v}=\operatorname{dis}_{u,v}$。这是定值。我们只需计算 $(u,v)$ 路径上点权最大值即可。可以树剖维护。

考虑 $k$ 在 $(u,v)$ 路径外情形。路径一定形如 $u\rightarrow p\rightarrow k\rightarrow p\rightarrow v$。即路径和等价于 $\operatorname{dis}_{u,v} +2\operatorname{dis}_{k,p}$，$p$ 在路径 $u,v$ 上。

因此，我们需要维护每个点 $p$ 的 $c_k-2\operatorname{dis}_{k,p}$ 最大值。这是经典问题，考虑二次扫描。首先从根节点开始遍历，更新每个点 $p$ 向下能延伸到的 $c_k-2\operatorname{dis}_{k,p}$ 最大值。第二次扫描，更新每个点 $p$ 向上能延伸到的最大值。最后对于每个点，向上和向下延伸的最大值取 $\max$ 即为答案。如下。

struct INIT
{
    void dfs1(int u,int fat,int sum)
    {
        dis[u] = sum; // 前缀和处理，后续计算两点距离时使用
        f1[u] = c[u];
        for(auto [v,w]:Edge[u])
        {
            if(v == fat) continue;
            dfs1(v,u,sum + w);
            f1[u] = max(f1[u],f1[v] - 2*w); // 儿子更新父亲
        }
    }
    void dfs2(int u,int fat)
    {
        for(auto [v,w]:Edge[u])
        {
            if(v == fat) continue;
            f[v] = max({c[v],f1[u]-2*w,f[u]-2*w}); //父亲更新儿子
            dfs2(v,u);
        }
    }
}init;

然后就做完了。每次询问代入上述公式直接算即可。我使用了树剖维护。

代码很长，见 剪切板。