这是李超线段树的一个简单应用。

考虑如何插入线段吧,设$dis_x$为$x$到根节点的距离。

在$s$这一侧的,直线应为$y=-a(dis_x-dis_s)+b$

在$t$这一侧的,直线应为$y=a(dis_s-2*dis_f+dis_x)+b$

之后直接树剖套李超线段树。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=1e5+5,Max=1e9,M=1010;
const ll inf=123456789123456789ll;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int dfn[N],ed[N],yss[N],cnt,top[N],tot,n,m;ll d[N];
struct line{ll k,b;}Line[N<<1];
struct Seg{ll mn;int id;}t[N<<3];
inline void update(int p){t[p].mn=min(t[p].mn,min(t[p<<1].mn,t[p<<1|1].mn));}
inline ll calc(int x,int pos){return Line[pos].k*d[yss[x]]+Line[pos].b;}
void build(int p,int l,int r)
{
    t[p].mn=inf;t[p].id=1;
    if(l==r)return ;
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
}
void change(int p,int l,int r,int L,int R,int x)
{
    int mid=l+r>>1;
    if(L<=l&&R>=r)
    {
        if(calc(l,x)<=calc(l,t[p].id)&&calc(r,x)<=calc(r,t[p].id)){t[p].id=x;t[p].mn=min(t[p].mn,min(calc(l,x),calc(r,x)));return ;}
        if(calc(l,x)>=calc(l,t[p].id)&&calc(r,x)>=calc(r,t[p].id))return ;
        if(Line[x].k<Line[t[p].id].k)
        {
            if(calc(mid,x)<=calc(mid,t[p].id))change(p<<1,l,mid,L,R,t[p].id),t[p].id=x;
            else change(p<<1|1,mid+1,r,L,R,x);
        }
        else
        {
            if(calc(mid,x)<=calc(mid,t[p].id))change(p<<1|1,mid+1,r,L,R,t[p].id),t[p].id=x;
            else change(p<<1,l,mid,L,R,x);
        }
        t[p].mn=min(t[p].mn,min(calc(l,x),calc(r,x)));update(p);return ;
    }
    if(L<=mid)change(p<<1,l,mid,L,R,x);
    if(R>mid)change(p<<1|1,mid+1,r,L,R,x);
    update(p);
}
ll query(int p,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)return t[p].mn;
    int mid=l+r>>1;ll mn=inf;
    if(Line[t[p].id].b!=inf)mn=min(calc(max(l,L),t[p].id),calc(min(r,R),t[p].id));
    if(L<=mid)mn=min(mn,query(p<<1,l,mid,L,R));
    if(R>mid)mn=min(mn,query(p<<1|1,mid+1,r,L,R));
    return mn;
}
struct edge{int y;ll w;int next;}a[N<<1];int len,last[N];
void ins(int x,int y,ll w){a[++len]=(edge){y,w,last[x]};last[x]=len;}
int fa[N],siz[N],son[N],dep[N];
void dfs1(int x)
{
    siz[x]=1,son[x]=0;
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=fa[x])
        {
            fa[y]=x;dep[y]=dep[x]+1;d[y]=d[x]+a[k].w;
            dfs1(y);
            siz[x]+=siz[y];if(siz[son[x]]<siz[y])son[x]=y;
        }
}
void dfs2(int x,int tp)
{
    dfn[x]=++cnt;yss[cnt]=x;top[x]=tp;
    if(son[x])dfs2(son[x],tp);
    for(int k=last[x],y;k;k=a[k].next)
        if((y=a[k].y)!=son[x]&&y!=fa[x])dfs2(y,y);
}
inline 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;
}
void uprange(int x,int y)
{
    while(top[x]!=top[y])change(1,1,n,dfn[top[x]],dfn[x],tot),x=fa[top[x]];
    change(1,1,n,dfn[y],dfn[x],tot);
}
ll ask(int x,int y)
{
    ll ans=inf;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans=min(ans,query(1,1,n,dfn[top[x]],dfn[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    return min(ans,query(1,1,n,dfn[y],dfn[x]));
}
int main()
{
    //freopen("game3.in","r",stdin);
    //freopen("game3.ans","w",stdout);
    qr(n),qr(m);
    for(int i=1;i<n;i++){int x,y;ll w;qr(x),qr(y),qr(w);ins(x,y,w),ins(y,x,w);}
    dep[1]=1;dfs1(1);dfs2(1,1);Line[++tot]=(line){0,inf};build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;qr(op),qr(x),qr(y);
        if(op==1)
        {
            ll A,B;qr(A),qr(B);int f=lca(x,y);
            Line[++tot]=(line){-A,B+A*d[x]};uprange(x,f);
            Line[++tot]=(line){A,B+A*(d[x]-(d[f]<<1))};uprange(y,f);
        }
        else
            qw(ask(x,y)),puts("");
    }
    return 0;
}