记录编号	587095	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2016 Round1] 游戏	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	2.661 s
提交时间	2024-03-12 22:14:16	内存使用	112.62 MiB

#include <bits/stdc++.h>
using namespace std;
//树剖+李超线段树 
#define ll long long
const int N = 3e5+10;
const ll inf = 1e17;
int n,m,cnt,num;
struct made{
    int ver,nx;ll ed;
}e[N<<1];
int hd[N],tot;
int fa[N],son[N],dep[N],size[N];
int dfn[N],rnk[N],top[N];
ll dis[N];
void add(int x,int y,ll z){
    tot++;
    e[tot].nx = hd[x],e[tot].ver = y,e[tot].ed = z,hd[x] = tot;
}
void dfs1(int x){
    size[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(dep[y])continue;
        dep[y] = dep[x] + 1,fa[y] = x,dis[y] = dis[x] + e[i].ed;
        dfs1(y);
        size[x] += size[y];
        if(!son[x] || size[y] > size[son[x]])son[x] = y;
    }
}
void dfs2(int x,int t){
    dfn[x] = ++cnt,rnk[cnt] = x;
    top[x] = t;
    if(!son[x])return;
    dfs2(son[x],t);
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(y != fa[x] && y != son[x])dfs2(y,y);
    }
}
int LCA(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    return x;
}


ll k[N],B[N];
struct LiChao_tree{
    ll mi[N<<5];int id[N<<5];
    void pre(){for(int i = 0;i <= 1e6;i++)mi[i] = 123456789123456789;}
    ll get(int x,int i){return k[i] * dis[rnk[x]] + B[i];}
    void pushup(int p){mi[p] = min(mi[p],min(mi[p<<1],mi[p<<1|1]));}
    void modify(int p,int l,int r,int x){
        int mid = l + r >> 1;
        if(get(mid,x) < get(mid,id[p]))swap(id[p],x);
        mi[p] = min(mi[p],min(get(l,id[p]),get(r,id[p])));
        if(get(l,x) < get(l,id[p]))modify(p<<1,l,mid,x);
        else if(get(r,x) < get(r,id[p]))modify(p<<1|1,mid+1,r,x);
        pushup(p);
    }
    void modify(int p,int l,int r,int L,int R,int x){
        if(L <= l && r <= R)return modify(p,l,r,x),void();
        int mid = l + r >> 1;
        if(L <= mid)modify(p<<1,l,mid,L,R,x);
        if(R > mid)modify(p<<1|1,mid+1,r,L,R,x);
        pushup(p);
    }
    ll query(int p,int l,int r,int L,int R){
        if(L <= l && r <= R)return mi[p];
        int mid = l + r >> 1;
        ll ans = min(get(max(l,L),id[p]),get(min(r,R),id[p]));//!!!
        if(L <= mid)ans = min(ans,query(p<<1,l,mid,L,R));
        if(R > mid)ans = min(ans,query(p<<1|1,mid+1,r,L,R));
        return ans;
    }
}t;


void cal(int x,int y){
    while(top[x] != top[y]){
        t.modify(1,1,n,dfn[top[x]],dfn[x],num);
        x = fa[top[x]];
    }
    t.modify(1,1,n,dfn[y],dfn[x],num);
}
ll calask(int x,int y){
    ll ans = 123456789123456789;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])swap(x,y);
        ans = min(ans,t.query(1,1,n,dfn[top[x]],dfn[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y])swap(x,y);
    ans = min(ans,t.query(1,1,n,dfn[x],dfn[y]));
    return ans;
}
int main(){
	freopen("menci_game.in","r",stdin);
    freopen("menci_game.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i < n;i++){
        int x,y;ll z;
        scanf("%d%d%lld",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    dep[1] = 1,dfs1(1),dfs2(1,1);
    t.pre();B[0] = 123456789123456789;
    for(int i = 1;i <= m;i++){
        int op,u,v;ll a,b;
        scanf("%d%d%d",&op,&u,&v);
        if(op == 2)printf("%lld\n",calask(u,v));
        else{
            scanf("%lld%lld",&a,&b);
            int x = LCA(u,v);
            k[++num] = -a,B[num] = a * dis[u] + b;
            cal(u,x);
            k[++num] = a,B[num] = a * (dis[u] - 2 * dis[x]) + b;
            cal(v,x);
        }
    }

	return 0;

}