solution
树剖后一段路径变成了若干链拼起来。自上而下和自下而上分别维护两棵李超线段树，每条链就是一段数轴，提前处理每个点两种方向上的在链内的横坐标。以最近公共祖先为界，把路径分成两段。从一个点向链的顶端跳就是区间加线段。每次跳完要把线段的截距增加一个横坐标偏移量乘上斜率，因为不同链横坐标不是统一的。
线段树要维护区间加线段和区间最值。每次插入线段都要用两端点更新区间的最值。每次查询 \([L,R]\) （设在链上横坐标为 \([Ls,Rs]\)）要在经过的所有区间把该区间和 \([Ls,Rs]\) 取交，然后用这个区间的最优线段（就是李超线段树维护的中点处取值最小的）在这个交区间的两端点的值更新答案。
建议先写链的情况（这个题数据链都是从 1 到 n 依次排点的），然后再上树。
建议写个暴力拍。
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long E;
const E inf=123456789123456789;
struct line{
E k,b;
line(E a=0,E y=inf){ k=a,b=y; }
inline E get(E x){ return k*x+b; }
};
const int N=400010;
struct segment{
line dat[N<<2];
E lp[N<<2],rp[N<<2],V[N<<2];
void pushup(int u){ lp[u]=lp[u<<1],rp[u]=rp[u<<1|1]; }
void build(int u,int l,int r,E *P){
dat[u]=line(0,inf); V[u]=inf;
if(l==r) return lp[u]=rp[u]=P[l],void();
int mid=(l+r)>>1;
build(u<<1,l,mid,P),build(u<<1|1,mid+1,r,P);
pushup(u);
}
void ins(int u,int l,int r,line val){
if(val.get(lp[u])>=dat[u].get(lp[u])&&
val.get(rp[u])>=dat[u].get(rp[u])) return ;
int mid=(l+r)>>1,h=(lp[u]==rp[u]?lp[u]:rp[u<<1]);
if(val.get(h)<dat[u].get(h)) swap(val,dat[u]);
V[u]=min({V[u],dat[u].get(lp[u]),dat[u].get(rp[u])});
//cout<<"INS "<<l<<' '<<r<<' '<<V[u]<<endl;
if(l==r) return ;
if(val.get(lp[u])<dat[u].get(lp[u])) ins(u<<1,l,mid,val);
if(val.get(rp[u])<dat[u].get(rp[u])) ins(u<<1|1,mid+1,r,val);
V[u]=min({V[u],V[u<<1],V[u<<1|1]});
}
void add(int u,int l,int r,int L,int R,line val){
if(L<=l&&r<=R) return ins(u,l,r,val);
int mid=(l+r)>>1;
if(L<=mid) add(u<<1,l,mid,L,R,val);
if(mid<R) add(u<<1|1,mid+1,r,L,R,val);
V[u]=min({V[u],V[u<<1],V[u<<1|1]});
//cout<<"ADD "<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<V[u]<<endl;
}
E ask(int u,int l,int r,int L,int R,E Ls,E Rs,int op){
if(L<=l&&r<=R){
return V[u];
}
int mid=(l+r)>>1;
E ret=inf;
if(op==2) ret=min({ret,dat[u].get(max(Ls,lp[u])),dat[u].get(min(Rs,rp[u]))});
else ret=min({ret,dat[u].get(min(Ls,lp[u])),dat[u].get(max(Rs,rp[u]))});
if(mid<R) ret=min(ret,ask(u<<1|1,mid+1,r,L,R,Ls,Rs,op));
if(L<=mid) ret=min(ret,ask(u<<1,l,mid,L,R,Ls,Rs,op));
return ret;
}
}seg1,seg2;
/*
- seg1 -> bottom to top
- seg2 -> top to bottom
*/
struct Edge{
int nxt,to,val;
}e[N<<1];
int hd[N],idx=2;
inline void add(int a,int b,int c){
e[idx].nxt=hd[a],e[idx].to=b,e[idx].val=c,hd[a]=idx++;
}
E dist[N];
int sz[N],dep[N],top[N],fa[N],hson[N],dfn[N],timestamp;
E mdep[N];
void dfs1(int u){
sz[u]=1;
for(int i=hd[u]; i; i=e[i].nxt){
int j=e[i].to;
if(j==fa[u]) continue;
fa[j]=u; dep[j]=dep[u]+1; dist[j]=dist[u]+e[i].val;
dfs1(j);
sz[u]+=sz[j];
if(sz[j]>sz[hson[u]]) hson[u]=j;
}
}
void dfs2(int u){
dfn[u]=++timestamp;
if(sz[u]==1) return ;
top[hson[u]]=top[u];
dfs2(hson[u]);
for(int i=hd[u]; i; i=e[i].nxt){
int j=e[i].to;
if(j==fa[u]||j==hson[u]) continue;
top[j]=j;
dfs2(j);
}
}
int n,m;
E P[N];
inline void tree_add(int a,int b,line L){
int x=a,y=b;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
int lca=dep[x]<dep[y]?x:y;
E d=dist[a]+dist[b]-2*dist[lca],D=0;
while(top[a]!=top[b]){
if(dep[top[a]]>dep[top[b]]){
seg1.add(1,1,n,dfn[top[a]],dfn[a],line(L.k,L.b+(D-(mdep[top[a]]-dist[a]))*L.k));
D+=dist[a]-dist[fa[top[a]]];
a=fa[top[a]];
}
else{
d-=(dist[b]-dist[top[b]]);
seg2.add(1,1,n,dfn[top[b]],dfn[b],line(L.k,L.k*d+L.b));
d-=(dist[top[b]]-dist[fa[top[b]]]);
b=fa[top[b]];
}
}
if(dep[a]>dep[b]){
seg1.add(1,1,n,dfn[b],dfn[a],line(L.k,L.b+(D-(mdep[top[a]]-dist[a]))*L.k));
}
else{
d-=(dist[b]-dist[a]);
seg2.add(1,1,n,dfn[a],dfn[b],line(L.k,L.k*(d-(dist[a]-dist[top[b]]))+L.b));
}
}
inline E tree_query(int a,int b){
E ret=inf;
while(top[a]!=top[b]){
if(dep[top[a]]>dep[top[b]]){
ret=min(ret,seg1.ask(1,1,n,dfn[top[a]],dfn[a],mdep[top[a]]-dist[top[a]],mdep[top[a]]-dist[a],1));
ret=min(ret,seg2.ask(1,1,n,dfn[top[a]],dfn[a],0,dist[a]-dist[top[a]],2));
a=fa[top[a]];
}
else{
ret=min(ret,seg2.ask(1,1,n,dfn[top[b]],dfn[b],0,dist[b]-dist[top[b]],2));
ret=min(ret,seg1.ask(1,1,n,dfn[top[b]],dfn[b],mdep[top[b]]-dist[top[b]],mdep[top[b]]-dist[b],1));
b=fa[top[b]];
}
}
if(dep[a]<dep[b]) swap(a,b);
ret=min({ret,seg1.ask(1,1,n,dfn[b],dfn[a],mdep[top[b]]-dist[b],mdep[top[a]]-dist[a],1),
seg2.ask(1,1,n,dfn[b],dfn[a],dist[b]-dist[top[b]],dist[a]-dist[top[a]],2)});
return ret;
}
signed main(){
cin>>n>>m;
for(int i=1; i<n; i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v,w),add(v,u,w);
}
dep[1]=top[1]=1;
dfs1(1),dfs2(1);
for(int i=1; i<=n; i++){
mdep[top[i]]=max(mdep[top[i]],dist[i]);
}
for(int i=1; i<=n; i++){
P[dfn[i]]=mdep[top[i]]-dist[i];
}
seg1.build(1,1,n,P);
for(int i=1; i<=n; i++){
P[dfn[i]]=dist[i]-dist[top[i]];
}
seg2.build(1,1,n,P);
/*
for(int ttt=1; ttt<=m; ttt++){
int opt,s,t,a,b;
scanf("%lld%lld%lld",&opt,&s,&t);
if(opt==1){
scanf("%lld%lld",&a,&b);
if(dfn[s]<=dfn[t]){
seg2.add(1,1,n,dfn[s],dfn[t],line(a,b-a*dist[s]));
}
else seg1.add(1,1,n,dfn[t],dfn[s],line(a,b-a*(mdep[top[s]]-dist[s])));
}
else{
if(dfn[s]>dfn[t]) swap(s,t);
printf("%lld\n",min(seg1.ask(1,1,n,dfn[s],dfn[t],mdep[top[s]]-dist[s],mdep[top[s]]-dist[t],1),
seg2.ask(1,1,n,dfn[s],dfn[t],dist[s],dist[t],2)));
}
}
return 0;
链的情况
*/
for(int ttt=0; ttt<m; ttt++){
int opt,s,t,a,b;
scanf("%lld%lld%lld",&opt,&s,&t);
if(opt==1){
scanf("%lld%lld",&a,&b);
tree_add(s,t,line(a,b));
}
else{
auto ans=tree_query(s,t);
printf("%lld\n",ans);
}
}
return 0;
}