目录

链接

https://www.luogu.org/problemnew/show/P4069

思路

树剖+超哥线段树
我已经自毙了，自闭了！！！！

update

上次抄了没认真看，这次考试又自毙了
是一个细节的处理上一次没处理

代码

#include <bits/stdc++.h>
#define ll long long
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const ll inf=123456789123456789LL;
const ll N=5e5+7;
ll read() {
    ll x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
ll n,m;
struct edge {
    ll v,nxt,q;
}e[N<<1];
ll head[N<<1],tot;
void add(ll u,ll v,ll q) {
    e[++tot].v=v;
    e[tot].q=q;
    e[tot].nxt=head[u];
    head[u]=tot;
}
ll fa[N],dep[N],son[N],siz[N];
ll dis[N];
void dfs1(ll u,ll f) {
    dep[u]=dep[f]+1;
    siz[u]=1;
    fa[u]=f;
    for(ll i=head[u];i;i=e[i].nxt) {
        ll v=e[i].v;
        if(v==f) continue;
        dis[v]=dis[u]+(ll)e[i].q;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
ll idx[N],top[N],js;
ll xxx[N];
void dfs2(ll u,ll topf) {
    idx[u]=++js;
    xxx[js]=u;
    top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(ll i=head[u];i;i=e[i].nxt) {
        ll v=e[i].v;
        if(!idx[v]) dfs2(v,v);
    }
}
struct node {
    ll l,r;
    ll a,b,mi;
}tr[N<<2];
void build(ll l,ll r,ll rt) {
    tr[rt].l=l,tr[rt].r=r;
    tr[rt].mi=tr[rt].b=inf;
    if(l==r) return;
    ll mid=(l+r)>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
}
ll f(ll a,ll b,ll x) {
    return a*dis[xxx[x]]+b;
}
#define f_l f(tr[rt].a,tr[rt].b,tr[rt].l)
#define f_r f(tr[rt].a,tr[rt].b,tr[rt].r)
void pushup(ll rt) {        
    tr[rt].mi=min(tr[rt].mi,min(tr[ls].mi,tr[rs].mi));
    tr[rt].mi=min(tr[rt].mi,min(f_l,f_r));
}
void modify(ll L,ll R,ll a,ll b,ll rt) {
    if(L<=tr[rt].l&&tr[rt].r<=R) {
        if(f_l<=f(a,b,tr[rt].l)&&f_r<=f(a,b,tr[rt].r)) return;
        if(f_l>f(a,b,tr[rt].l)&&f_r>f(a,b,tr[rt].r)) {
            tr[rt].a=a;
            tr[rt].b=b;
            tr[rt].mi=min(tr[rt].mi,min(f_l,f_r));
            return; 
        }
        ll mid=(tr[rt].l+tr[rt].r)>>1;

        if(tr[rt].a<=a) {
            if(f(tr[rt].a,tr[rt].b,mid)>=f(a,b,mid)) {
                swap(tr[rt].a,a);
                swap(tr[rt].b,b);
                modify(L,R,a,b,rs);
            } else modify(L,R,a,b,ls);
        } else {
            if(f(tr[rt].a,tr[rt].b,mid)>=f(a,b,mid)) {
                swap(tr[rt].a,a);
                swap(tr[rt].b,b);
                modify(L,R,a,b,ls);
            } else modify(L,R,a,b,rs);
        }
         tr[rt].mi= min(min(tr[ls].mi, tr[rs].mi), min(f_l,f_r));
        // pushup(rt);
        return;
    }
    ll mid=(tr[rt].l+tr[rt].r)>>1;
    if(L<=mid) modify(L,R,a,b,ls);
    if(R>mid) modify(L,R,a,b,rs);
    pushup(rt);
}

ll query(ll L,ll R,ll rt) {
    if(L<=tr[rt].l&&tr[rt].r<=R) {
        return tr[rt].mi;
    }
    ll mid=(tr[rt].l+tr[rt].r)>>1;
    ll ans=inf;
    ans=min(ans,min(f(tr[rt].a,tr[rt].b,max(L,tr[rt].l)),f(tr[rt].a,tr[rt].b,min(tr[rt].r,R))));
    if(L<=mid) ans=min(ans,query(L,R,ls));
    if(R>mid) ans=min(ans,query(L,R,rs));
    return ans;
}
ll lca(ll x,ll 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;
}
void C(ll x,ll y,ll a,ll b) {
    while(top[x]!=top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        modify(idx[top[x]],idx[x],a,b,1);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(idx[x],idx[y],a,b,1);
}
void Q(ll x,ll y) {
    ll ans=inf;
    while(top[x]!=top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        ans=min(ans,query(idx[top[x]],idx[x],1));
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=min(ans,query(idx[x],idx[y],1));
    printf("%lld\n",ans);
}
int main() {        
    n=read(),m=read();
    for(ll i=1;i<n;++i) {
        ll x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    while(m--) {
        ll opt=read();
        if(opt==1) {
            ll s=read(),t=read();
            ll A=read(),B=read();
            ll dsr=lca(s,t);
            C(s,dsr,(ll)-A,1LL*dis[s]*A+B);
            C(dsr,t,(ll)A,1LL*dis[s]*A-2LL*A*dis[dsr]+B);
        } else {
            ll s=read(),t=read();
            Q(s,t);
        }
    }
    return 0;
}