题解：P11324 【MX-S7-T2】「SMOI-R2」Speaker

· · 题解

思路

容易想到无论起终点如何每个点最优的中转方案是确定的，因此可以设 f_i 为点 i 的最优方案的贡献，比较好想 f_i=a_x+d(i,x)，考虑简单换根 dp 解决。假设存在一父子关系点对 x,y，设存在一点 z\in subtree_y，容易发现若 z 不是 y 的最优中转点，则其一定不是 x 的最优中转点。也就是说，每个点的最优中转点的候选只有相邻点的最优中转点或自身。那么先以 1 为根正常 dp 跑出 f_1 的值，然后再倒着转移一遍，即用父亲更新儿子，就可以在 \mathcal{O(n)} 的时间内求出每个点的 f 值。

此时答案已经被拆分成了 a_{x_i}+a_{y_i}-d(x_i,y_i)+\max_{u\in x_i\rightarrow y_i} f_i，其中 x_i\rightarrow y_i 表示 x_i 到 y_i 的路径。发现前三项都是固定的，最后一项只需要找到树上路径最大值即可，考虑树剖维护即可。

然后就做完了，时间复杂度 \mathcal{O(n\log^2 n)}。

注意一个易错小细节，树剖求 lca 和统计答案时用的 deep 数组不要和树上差分的 dis 数组搞混！猜猜谁因为这个挂了 12pts。

实现

#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 998244353;
int n, m;
int a[N];
int dfn[N], dt, fx[N], top[N], son[N], siz[N], dep[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
ll w[N << 1], dis[N], wt[N], f[N], v[N << 2];
namespace Wisadel
{
    inline void Wadd(int u, int v, ll val)
    {
        to[++cnt] = v;
        w[cnt] = val;
        ne[cnt] = hh[u];
        hh[u] = cnt;
    }
    inline void Wdfs(int u, int fa)
    {
        fx[u] = fa, siz[u] = 1, dep[u] = dep[fa] + 1;
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            dis[v] = dis[u] + w[i];
            Wdfs(v, u);
            siz[u] += siz[v];
            if(siz[v] > siz[son[u]]) son[u] = v;
        }
    }
    inline void Wdfs2(int u, int tpf)
    {
        dfn[u] = ++dt, wt[dt] = f[u], top[u] = tpf;
        if(son[u]) Wdfs2(son[u], tpf);
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fx[u] || v == son[u]) continue;
            Wdfs2(v, v);
        }
    }
    inline void Wdfs3(int u, int fa)
    {
        f[u] = a[u];
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            Wdfs3(v, u);
            f[u] = max(f[u], f[v] - 2 * w[i]);
        }
    }
    inline void Wdfs4(int u, int fa)
    {
        for(int i = hh[u]; i != -1; i = ne[i])
        {
            int v = to[i];
            if(v == fa) continue;
            f[v] = max(f[v], f[u] - 2 * w[i]);
            Wdfs4(v, u);
        }
    }
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    inline void Wpushup(int rt){v[rt] = max(v[ls], v[rs]);}
    inline void Wbuild(int rt, int l, int r)
    {
        if(l == r)
        {
            v[rt] = wt[l];
            return ;
        }
        Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
        Wpushup(rt);
    }
    inline ll Wq(int rt, int l, int r, int x, int y)
    {
        if(x <= l && r <= y) return v[rt];
        ll res = -2e18;
        if(x <= mid) res = max(res, Wq(ls, l, mid, x, y));
        if(y > mid) res = max(res, Wq(rs, mid + 1, r, x, y));
        return res;
    }
    #undef ls
    #undef rs
    #undef mid
    inline int Wlca(int x, int y)
    {
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            x = fx[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        return x;
    }
    inline ll Wque(int x, int y)
    {
        ll res = -2e18;
        while(top[x] != top[y])
        {
            if(dep[top[x]] < dep[top[y]]) swap(x, y);
            res = max(res, Wq(1, 1, n, dfn[top[x]], dfn[x]));
            x = fx[top[x]];
        }
        if(dep[x] > dep[y]) swap(x, y);
        res = max(res, Wq(1, 1, n, dfn[x], dfn[y]));
        return res;
    }
    inline ll Wd(int u, int v){return dis[u] + dis[v] - 2 * dis[Wlca(u, v)];}
    short main()
    {
        n = qr, m = qr;
        memset(hh, -1, sizeof hh);
        fo(i, 1, n) a[i] = qr;
        fo(i, 1, n - 1)
        {
            int a = qr, b = qr; ll c = qr;
            Wadd(a, b, c), Wadd(b, a, c);
        }
        Wdfs(1, 0), Wdfs3(1, 0), Wdfs4(1, 0), Wdfs2(1, 1);
        Wbuild(1, 1, n);
        fo(i, 1, m)
        {
            int x = qr, y = qr;
            ll ans = a[x] + a[y] - Wd(x, y) + Wque(x, y);
            printf("%lld\n", ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// All talk and never answer

完结撒花~