李超树的模板题。
考虑题目给出的 \(a \times dis + b\)，整体不好处理，可以把 \(s\) 到 \(t\) 的路径从 \(p \gets lca(s,t)\) 处分开。左边是 \(-a \times dis_i + (a \times dis_s + b)\)，右边是 \(a \times dis_i + (a \times (dis_s - 2 \times dis_p) + b)\)，都是以 \(dis_i\) 为自变量的一次函数，可以用李超树维护。
更大的问题在于查询：树上的路径最小值在序列上就是区间最小。这意味着，我们要在李超树上像普通线段树一样维护一个区间最小值。然而，因为李超树主要维护线段，无法进行标记的下传和上推，我们必须引入一个技巧——标记永久化。
访问到一个区间，如果查询区间完全包含它，直接取出。如果不完全包含，就要用本区间的信息实时更新答案。在此题中，就呈现为 p->minx=min(p->minx,min(p->ls->minx,p->rs->minx)); 的形式。
李超树和树剖老生常谈，不再赘述细节。
下面是 AC 代码核心部分：
//计算点值
inline LL calc(int id,int x){return k[id]*dis[f[x]]+b[id];}
//线段树主体（略去build()和外部调用函数）
struct segtree{
int l,r;LL id,minx;segtree *ls,*rs;
segtree(){ls=rs=0,minx=INF,id=1;}
#define mid (((p->l)+(p->r))>>1)
}*rt;
inline void refresh(segtree *p){
p->minx=min(p->minx,min(p->ls->minx,p->rs->minx));
}
void _change(segtree *p,int l,int r,int id){
if(l<=p->l&&p->r<=r){
if(calc(id,p->l)<=calc(p->id,p->l)&&calc(id,p->r)<=calc(p->id,p->r)){
p->id=id;
p->minx=min(p->minx,min(calc(id,p->l),calc(id,p->r)));//标记永久化*1
return;
}
//略去按照斜率和中点讨论的部分
p->minx=min(p->minx,min(calc(id,p->l),calc(id,p->r)));//标记永久化*2
refresh(p);return;
}
if(l<=mid) _change(p->ls,l,r,id);
if(r>mid) _change(p->rs,l,r,id);
refresh(p);
}
LL _query(segtree *p,int l,int r){
if(l<=p->l&&p->r<=r) return p->minx;
LL ans=INF;
if(b[p->id]!=INF)
ans=min(calc(p->id,max(l,p->l)),calc(p->id,min(r,p->r)));//标记永久化*3
if(l<=mid) ans=min(ans,_query(p->ls,l,r));
if(r>mid) ans=min(ans,_query(p->rs,l,r));
return ans;
}
//main()函数调用部分
k[++cnt]=0,b[cnt]=INF,build(rt=new segtree,1,n);
while(m--){
int op=rd(),s=rd(),t=rd(),p=lca(s,t);
if(op==1){
int x=rd(),y=rd();
k[++cnt]=-x,b[cnt]=y+x*dis[s];change(s,p,cnt);
k[++cnt]=x,b[cnt]=y+x*(dis[s]-dis[p]*2);change(t,p,cnt);
}
else printf("%lld\n",query(s,t));
}