RT

蒻蒟打的是树剖 + 李超，由于懒就直接用 fill 把最小值 mn 填了：

#include <bits/stdc++.h>
#define STC static
#define fi first
#define se second
#define FF std::function
using LL = long long;
using PII = std::pair<int, int>;
const int N = 1e5 + 100;
const LL INF = 123456789123456789;
int n, m, ctl = 0, bid[N];
std::vector<PII> G[N];
LL dis[N];
struct Line
{
    int k;
    LL b;
    LL calc(int x){ return dis[bid[x]] * k + b; }
} li[N << 1];
namespace LC
{
    using std::max;
    using std::min;
    int id[N << 2];
    LL mn[N << 2];
    #define mid (l + r >> 1)
    #define lc (u << 1)
    #define rc (u << 1 | 1)
    bool judge(int a, int b, int x){ return li[a].calc(x) > li[b].calc(x); }
    void upd(int u, int l, int r, int ql, int qr, int d)
    {
        STC FF<void(int, int, int)> up = [&](int u, int l, int r)
        {
            mn[u] = min(mn[u], min(li[id[u]].calc(l), li[id[u]].calc(r)));
            mn[u] = min(mn[u], min(mn[lc], mn[rc])); 
        } ;
        if (l >= ql && r <= qr)
        {
            if (judge(id[u], d, mid)) std::swap(id[u], d);
            if (judge(id[u], d, l)) upd(lc, l, mid, ql, qr, d);
            if (judge(id[u], d, r)) upd(rc, mid + 1, r, ql, qr, d);
            return up(u, l, r); 
        }
        if (ql <= mid) upd(lc, l, mid, ql, qr, d);
        if (qr > mid) upd(rc, mid + 1, r, ql, qr, d);
        up(u, l, r);
    }
    LL ask(int u, int l, int r, int ql, int qr)
    {
        if (l >= ql && r <= qr) return mn[u];
        LL res = min(li[id[u]].calc(max(l, ql)), li[id[u]].calc(min(r, qr)));
        if (ql <= mid) res = min(res, ask(lc, l, mid, ql, qr));
        if (qr > mid) res = min(res, ask(rc, mid + 1, r, ql, qr));
        return res;
    }
    #undef mid
    #undef lc
    #undef rc
}
namespace TCS //TreeChainSegmentation
{
    
    int fa[N], top[N], id[N], cnt, dep[N], si[N], son[N];
    void prev()
    {
        FF<void(int, int, int, LL)> dfs1 = [&](int x, int f, int d, LL di)
        {
            fa[x] = f, dep[x] = d, dis[x] = di, si[x] = 1;
            for (PII e : G[x]) if (e.fi != f)
            {
                dfs1(e.fi, x, d + 1, di + e.se);
                si[x] += si[e.fi];
                if (si[e.fi] > si[son[x]]) son[x] = e.fi;
            }
        } ;
        FF<void(int, int)> dfs2 = [&](int x, int t)
        {
            top[x] = t, id[x] = ++cnt, bid[cnt] = x;
            if (!son[x]) return ;
            dfs2(son[x], t);
            for (PII e : G[x]) if (e.fi != fa[x] && e.fi != son[x]) dfs2(e.fi, e.fi);
        } ;
        dfs1(1, 0, 1, 0), dfs2(1, 1);
    }
    void change(int s, int t, int a, int b)
    {
        STC FF<int(int, int)> lca = [&](int x, int y)
        {
            while (top[x] != top[y]) dep[top[x]] > dep[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
            return dep[x] > dep[y] ? y : x;
        } ; 
        STC FF<void(int, int, int)> modify = [&](int x, int y, int d)
        {
            while (top[x] != top[y]) LC::upd(1, 1, n, id[top[x]], id[x], d), x = fa[top[x]];
            LC::upd(1, 1, n, id[y], id[x], d);
        } ;
        int ff = lca(s, t);
        li[++ctl] = {-a, dis[s] * a + b}, modify(s, ff, ctl);
        li[++ctl] = {a, (dis[s] - (dis[ff] << 1)) * a + b}, modify(t, ff, ctl);
    }
    LL ask(int s, int t)
    {
        LL res = INF;
        while (top[s] != top[t])
        {
            if (dep[top[s]] < dep[top[t]]) std::swap(s, t);
            res = std::min(res, LC::ask(1, 1, n, id[top[s]], id[s])), s = fa[top[s]];
        }
        if (id[s] > id[t]) std::swap(s, t);
        return std::min(res, LC::ask(1, 1, n, id[s], id[t]));
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1, u, v, w; i < n; ++i)
    {
        scanf("%d %d %d", &u, &v, &w);
        G[u].push_back({v, w}), G[v].push_back({u, w});
    }
    TCS::prev(), li[0] = {0, INF};
    std::fill(LC::mn, LC::mn + (N << 2), INF);
    for (int op, s, t, a, b; m--; )
    {
        scanf("%d %d %d", &op, &s, &t);
        if (op == 1)
        {
            scanf("%d %d", &a, &b);
            TCS::change(s, t, a, b);
        }
        else printf("%lld\n", TCS::ask(s, t));
    }
    return 0;
}

可以看到 $24$ 行的 LL mn[N << 2] 和 $121$ 行的 std::fill(LC::mn, LC::mn + (N << 2), INF) ,然后交了， $95pts$

但把它们改成 LL mn[N << 4] 和 std::fill(LC::mn, LC::mn + (N << 4), INF) （就是把空间开大）就 AC 了

那么蒻蒟我就很不李姐了，不是说好的线段树空间开四倍吗？为啥挂了？

求 dalao 解惑