瞪了 1h 了

Link

#include <bits/stdc++.h>

// #define int long long
#define ll long long
#define ull unsigned long long
#define db double
#define ld long double
#define rep(i,l,r) for (int i = (int)(l); i <= (int)(r); ++ i )
#define rep1(i,l,r) for (int i = (int)(l); i >= (int)(r); -- i )
#define il inline
#define fst first
#define snd second
#define ptc putchar
#define Yes ptc('Y'),ptc('e'),ptc('s'),puts("")
#define No ptc('N'),ptc('o'),puts("")
#define YES ptc('Y'),ptc('E'),ptc('S'),puts("")
#define NO ptc('N'),ptc('O'),puts("")
#define vi vector<int>
#define pb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define me(a,x) memset(a,x,sizeof a)
#define get(x) ((x - 1) / len + 1)
#define debug() puts("------------")

using namespace std;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef pair<ll,ll> PLL;
namespace szhqwq {
    template<class T> il void read(T &x) {
        x = 0; T f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
        while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
        x *= f;
    }
    template<class T,class... Args> il void read(T &x,Args &...x_) { read(x); read(x_...); }
    template<class T> il void print(T x) {
        if (x < 0) ptc('-'), x = -x; 
        if (x > 9) print(x / 10); ptc(x % 10 + '0');
    }
    template<class T,class T_> il void write(T x,T_ ch) { print(x); ptc(ch); }
    template<class T,class T_> il void chmax(T &x,T_ y) { x = x < (T)y ? (T)y : x; }
    template<class T,class T_> il void chmin(T &x,T_ y) { x = x > (T)y ? (T)y : x; }
    template<class T,class T_,class T__> il T qmi(T a,T_ b,T__ p) {
        T res = 1; while (b) {
            if (b & 1) res = res * a % p;
            a = a * a % p; b >>= 1;
        } return res;
    }
    template<class T> il T gcd(T a,T b) { if (!b) return a; return gcd(b,a % b); }
    template<class T,class T_> il void exgcd(T a, T b, T_ &x, T_ &y) {
        if (b == 0) { x = 1; y = 0; return; }
        exgcd(b,a % b,y,x); y -= a / b * x; return ;
    }
    template<class T,class T_> il T getinv(T x,T_ p) { 
        T inv,y; exgcd(x,(T)p,inv,y);
        inv = (inv + p) % p; return inv;
    }
} using namespace szhqwq;
const int N = 2e5 + 10,inf = 1e9,mod = 998244353;
const ull base = 131,base_ = 233;
const ll inff = 1e18;
const db eps = 1e-6;
int n,m,tot,dfn[N]; ll dis[N];
int h[N],e[N],ne[N],w[N],idx;
int siz[N],son[N],d[N],id[N],top[N],cnt,fa[N];
struct Line {
    ll k,b;
    il ll calc(ll pos) { return k * pos + b; }
} a[N];
struct node { 
    int id; ll mn;
    node() { mn = 123456789123456789ll; id = 0; }
} tr[N << 2];

il bool check(int i,int j,int pos) {
    ll yi = a[i].calc(dis[dfn[pos]]),yj = a[j].calc(dis[dfn[pos]]);
    if (yi <= yj) return 1;
    return 0;
}

il void pushup(int u,int l,int r) {
    tr[u].mn = min(a[tr[u].id].calc(dis[dfn[l]]),a[tr[u].id].calc(dis[dfn[r]]));
    if (l != r) chmin(tr[u].mn,min(tr[u << 1].mn,tr[u << 1 | 1].mn));
    return ;
}

il void update(int u,int l,int r,int id) {
    int mid = l + r >> 1;
    if (check(id,tr[u].id,mid)) swap(tr[u].id,id);
    if (check(id,tr[u].id,l)) update(u << 1,l,mid,id);
    if (check(id,tr[u].id,r)) update(u << 1 | 1,mid + 1,r,id);
    pushup(u,l,r);
    return ;
}

il void modify(int u,int l,int r,int L,int R,int id) {
    if (L <= l && r <= R) {
        if (check(id,tr[u].id,l) && check(id,tr[u].id,r)) return tr[u].id = id,pushup(u,l,r),void();
        if (check(tr[u].id,id,l) && check(tr[u].id,id,r)) return ;
        update(u,l,r,id);
        pushup(u,l,r);
        return ;
    }
    int mid = l + r >> 1;
    if (L <= mid) modify(u << 1,l,mid,L,R,id);
    if (mid < R) modify(u << 1 | 1,mid + 1,r,L,R,id);
    pushup(u,l,r);
    return ;
}

il ll query(int u,int l,int r,int L,int R) {
    if (L <= l && r <= R) return tr[u].mn;
    int mid = l + r >> 1; ll ret = min(a[tr[u].id].calc(max(l,L)),a[tr[u].id].calc(min(r,R)));
    if (L <= mid) chmin(ret,query(u << 1,l,mid,L,R));
    if (mid < R) chmin(ret,query(u << 1 | 1,mid + 1,r,L,R));
    return ret;
}

il void add(int a,int b,int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
    return ;
}

il void dfs(int u,int f,int dep) {
    d[u] = dep;
    fa[u] = f;
    siz[u] = 1;
    int mx = -1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == f) continue;
        dis[j] = dis[u] + w[i];
        dfs(j,u,dep + 1);
        siz[u] += siz[j];
        if (siz[j] > mx) mx = siz[j],son[u] = j;
    }
    return ;
}

il void dfss(int u,int t) {
    top[u] = t;
    id[u] = ++ cnt;
    dfn[cnt] = u;
    if (!son[u]) return ;
    dfss(son[u],t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfss(j,j);
    }
    return ;
}

il int LCA(int x,int y) {
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    if (d[x] > d[y]) swap(x,y);
    return x;
}

il void modify_Range(int x,int y) {
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x,y);
        modify(1,1,n,id[top[x]],id[x],tot);
        x = fa[top[x]];
    }
    if (d[x] > d[y]) swap(x,y);
    modify(1,1,n,id[x],id[y],tot);
    return ;
}

il ll query_Range(int x,int y) {
    ll ret = inff;
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x,y);
        chmin(ret,query(1,1,n,id[top[x]],id[x]));
        x = fa[top[x]];
    }
    if (d[x] > d[y]) swap(x,y);
    chmin(ret,query(1,1,n,id[x],id[y]));
    return ret;
} 

il void solve() {
    //------------code------------
    read(n,m); me(h,-1);
    rep(i,1,n - 1) {
        int a,b,c; read(a,b,c);
        add(a,b,c); add(b,a,c);
    }
    a[0] = {0,123456789123456789ll};
    dfs(1,0,1); dfss(1,1);
    while (m -- ) {
        int op,s,t; ll x,y; read(op,s,t);
        if (op == 1) {
            read(x,y);
            int lca = LCA(s,t);
            a[++ tot] = {-x,x * dis[s] + y}; modify_Range(s,lca);
            a[++ tot] = {x,x * (dis[s] - 2ll * dis[lca]) + y}; modify_Range(lca,t);
        } else write(query_Range(s,t),'\n');
    }
    return ;
}

il void init() {
    return ;
}

signed main() {
    // init();
    int _ = 1;
    // read(_);
    while (_ -- ) solve();
    return 0;
}