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;

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

代码很长，见 剪切板。