题解：P14588 [LNCPC 2025] 前线支援

· · 题解

树剖常数小，BIT 小常数，两只老哥拿下最优解（截止 2026/11/6）。

令 d_u 表示 u 到根的距离，siz_u 表示 u 子树的大小。

思考怎么去维护操作 1。设 z = LCA (x, y)。

先仅考虑 x \neq z 的情况：此时对于 x 子树内的每个点 i，贡献为 d_u + d_y - d_z \times 2。不难发现 a_u 始终为 k \times d_u + b 的形式，在 dfs 序上考虑每次操作相当于在 k, b 上区间加。

再考虑 x = z 的情况。这时对 x 子树内的点 u 的贡献为 d_u + d_y - d_k \times 2 的形式，由于 d_k 的变化难以再使用同一套维护方式。我们考虑把贡献写成如下形式：

d_u + d_y - d_x \times 2 - (d_k - d_x) \times 2

让我们头疼的是最后一项。转而考虑不同 k 对 u 的贡献，相当于标记了 y 到 x 上的所有边，每条边 (fa_u, u) 对 u 子树内的所有点产生 -w_u \times 2 的贡献。

看起来操作 1 已经变得简单了，考虑怎么做操作 2。对于子树 x 内的所有边 (fa_u, u)，其贡献为 -w_u \times siz_u \times 2；而对于 x 到根上的每条边 (fa_u, u)，其贡献为 -w_u \times siz_x \times 2。于是我们在 dfs 序上需要维护的是 w_u 和 w_u \times siz_u 状物进行区间加减，这也是比较简单的。

两部分贡献均可以用树状数组完成（注意要区间修改区间查询，所以实际上需要维护七棵 BIT），加上树剖是 \mathcal {O} (n \log ^ 2 n) 的。

%:include <bits/stdc++.h>
using namespace std;

# define il inline

using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

namespace fast {

    constexpr size_t L = 1u << 20;
    char ibuf [L];
    size_t ip = 0, ilen;

    il char gc () {
        if (__builtin_expect (ip >= ilen, 0)) {
            ilen = fread (ibuf, sizeof (char), L, stdin);
            ip = 0;
            if (!ilen)
                return 0;
        }
        return ibuf [ip++];
    }

    char obuf [L];
    size_t op = 0;

    il void pc (char c) {
        if (__builtin_expect (op == L, 0)) {
            fwrite (obuf, sizeof (char), op, stdout);
            op = 0;
        }
        obuf [op++] = c;
    }

    struct flusher {
        ~flusher () {
            if (op) {
                fwrite (obuf, sizeof (char), op, stdout);
            }
        }
    } __flusher__;
}

# define getchar fast :: gc
# define putchar fast :: pc

template <class _Tp>
il void read (_Tp &x) {
    char ch = getchar ();
    int negative = 0;
    while (!isdigit (ch)) {
        negative = ch == '-';
        ch = getchar ();
    }
    x = 0;
    while (isdigit (ch)) {
        x = x * 10 + (ch & 15);
        ch = getchar ();
    }
    negative ? (x = -x) : 0;
}

template <class _Tp>
il void write (_Tp x) {
    if (x == 0) {
        putchar ('0');
        return ;
    }
    if (x < 0) {
        putchar ('-');
        x = -x;
    }
    static char stk [32];
    int tp = 0;
    while (x) {
        stk [++tp] = x % 10 + 48;
        x /= 10;
    }
    while (tp)
        putchar (stk [tp--]);
}

constexpr int N = 5e5 + 5;

int n, q, fa [N], w [N];
vector <int> edg [N];

int siz [N], son [N], d [N];
void pre_dfs (int u, int fa) {
    d [u] = d [fa] + w [u];
    siz [u] = 1;
    for (const int v : edg [u]) {
        pre_dfs (v, u);
        siz [u] += siz [v];
        if (siz [v] > siz [son [u]])
            son [u] = v;
    }
}

constexpr int Lg = 20;

int top [N], dfn [N], out [N], rnk [N], tim;
int g [Lg][N];
void top_dfs (int u, int tp) {
    top [u] = tp;
    rnk [dfn [u] = ++tim] = u;
    g [0][tim] = fa [u];
    if (son [u])
        top_dfs (son [u], tp);
    for (const int v : edg [u])
        if (v != son [u])
            top_dfs (v, v);
    out [u] = tim;
}

il int getm (int x, int y) {
    return dfn [x] < dfn [y] ? x : y;
}

i64 pred [N], preh [N], pres [N];

void init () {
    for (int i = 1; (1 << i) <= n; i++) {
        const int gap = 1 << i;
        const int half = 1 << i - 1;
        for (int j = 1; j + gap - 1 <= n; j++)
            g [i][j] = getm (g [i - 1][j], g [i - 1][j + half]);
    }

    for (int i = 1; i <= n; i++) {
        const int u = rnk [i];
        pred [i] = pred [i - 1] + d [u];
        preh [i] = preh [i - 1] + w [u];
        pres [i] = pres [i - 1] + w [u] * siz [u];
    }
}

il int lca (int u, int v) {
    if (u == v)
        return u;
    if ((u = dfn [u]) > (v = dfn [v]))
        swap (u, v);
    const int k = __lg (v - u++);
    return getm (g [k][u], g [k][v - (1 << k) + 1]);
}

namespace bit1 {

    i64 tc0 [N], tc1 [N];
    i64 tb0 [N], tb1 [N];

    il void add_c (int i, i64 v) {
        const i64 vd = v * pred [i - 1];
        for (int j = i; j <= n + 1; j += j & -j) {
            tc0 [j] += v;
            tc1 [j] += vd;
        }
    }
    il void add_b (int i, i64 v) {
        const i64 vj = v * i;
        for (int j = i; j <= n + 1; j += j & -j) {
            tb0 [j] += v;
            tb1 [j] += vj;
        }
    }
    il void add (int l, int r, i64 b) {
        add_c (l, 1);
        if (r < n)
            add_c (r + 1, -1);
        add_b (l, b);
        if (r < n)
            add_b (r + 1, -b);
    }

    il i64 pref_c (int x) {
        i64 s0 = 0, s1 = 0;
        for (int i = x; i; i -= i & -i) {
            s0 += tc0 [i];
            s1 += tc1 [i];
        }
        return pred [x] * s0 - s1;
    }
    il i64 pref_b (int x) {
        i64 s0 = 0, s1 = 0;
        for (int i = x; i; i -= i & -i) {
            s0 += tb0 [i];
            s1 += tb1 [i];
        }
        return (x + 1) * s0 - s1;
    }
    il i64 query (int l, int r) {
        return pref_c (r) - pref_c (l - 1)
             + pref_b (r) - pref_b (l - 1);
    }
}

namespace bit2 {

    i64 bt0 [N], bth [N], bts [N];

    il void add_b (int i, i64 v) {
        const i64 vh = v * preh [i - 1];
        const i64 vs = v * pres [i - 1];
        for (int j = i; j <= n + 1; j += j & -j) {
            bt0 [j] += v;
            bth [j] += vh;
            bts [j] += vs;
        }
    }
    il void add (int l, int r) {
        add_b (l, 1);
        if (r < n)
            add_b (r + 1, -1);
    }

    il i64 pref_t (int x) {
        i64 s0 = 0, sh = 0;
        for (int i = x; i; i -= i & -i) {
            s0 += bt0 [i];
            sh += bth [i];
        }
        return preh [x] * s0 - sh;
    }
    il i64 pref_s (int x) {
        i64 s0 = 0, ss = 0;
        for (int i = x; i; i -= i & -i) {
            s0 += bt0 [i];
            ss += bts [i];
        }
        return pres [x] * s0 - ss;
    }
    il i64 query_t (int l, int r) {
        return pref_t (r) - pref_t (l - 1);
    }
    il i64 query_s (int l, int r) {
        return pref_s (r) - pref_s (l - 1);
    }
}

void operate (int x, int y) {
    const int z = lca (x, y);
    const i64 b = d [y] - d [z] * 2;
    bit1 :: add (dfn [x], out [x], b);
    if (x == z) {
        while (top [y] != top [x]) {
            bit2 :: add (dfn [top [y]], dfn [y]);
            y = fa [top [y]];
        }
        if (x != y)
            bit2 :: add (dfn [x] + 1, dfn [y]);
    }
}

void query (int x) {
    const i64 rs = bit1 :: query (dfn [x], out [x]);
    const i64 rp = bit2 :: query_s (dfn [x], out [x]);
    const int sz = siz [x];
    i64 ans = rs - rp * 2;
    if (x != 1) {
        for (x = fa [x]; top [x] != 1; ) {
            ans -= bit2 :: query_t (dfn [top [x]], dfn [x]) * sz * 2;
            x = fa [top [x]];
        }
        if (x > 1)
            ans -= bit2 :: query_t (dfn [1] + 1, dfn [x]) * sz * 2;
    }
    write (ans);
    putchar ('\n');
}

int main ( /* QAQ */ ) {

    # ifndef ONLINE_JUDGE

    freopen ("ex_rescue_3.in", "r", stdin);
    freopen ("tmp.out", "w", stdout);

    # endif

    read (n), read (q);
    for (int i = 2; i <= n; i++) {
        read (fa [i]), read (w [i]);
        edg [fa [i]].emplace_back (i);
    }

    pre_dfs (1, 0);
    top_dfs (1, 1);
    init ();

    for (int i = 1; i <= q; i++) {
        int cmd;
        read (cmd);

        if (cmd == 1) {
            int x, y;
            read (x), read (y);
            operate (x, y);
        }

        if (cmd == 2) {
            int x;
            read (x);
            query (x);
        }
    }

    fprintf (stderr, "%.3lf second (s)\n",
        1. * clock () / CLOCKS_PER_SEC);
    return 0;
}

提交记录。比 Solwek 的单老哥做法快近一倍。

感谢 Deepseek 教我如何把线段树改成树状数组。