每一次加的是一个一次函数，一些呈一次函数的线段求最小值，显然用到李超线段树。
然后把维护序列的李超线段树强行上树，就直接套上树剖就可以了。
至于李超树如何区间查询，因为一次函数线段的最小值一定会取在两端，所以对于每一个点维护它和它的子树中所有线段的最低点，递归的时候如果当前区间被询问区间包含就直接返回维护的最低点，对于经过的线段再考虑它是否能够更新答案。
复杂度\(O(nlog^3n)\)可能自带小常数就过了吧……
#include//this code is written by Itstusing namespace std;int read(){ int a = 0; bool f = 0; char c = getchar(); while(!isdigit(c)){f = c == '-'; c = getchar();} while(isdigit(c)){a = a * 10 + c - 48; c = getchar();} return f ? -a : a;}#define int long long#define ld long doublestruct line{ int k , b; line(int _k = 0 , int _b = 123456789123456789ll) : k(_k) , b(_b){}};ld sect(line a , line b){return 1.0 * (a.b - b.b) / (b.k - a.k);}const int _ = 1e5 + 7;struct Edge{ int end , upEd , w;}Ed[_ << 1];int head[_] , fa[_] , dep[_] , len[_] , dfn[_] , ind[_] , top[_] , sz[_] , son[_];int N , M , cntEd , ts;void addEd(int a , int b , int c){ Ed[++cntEd] = (Edge){b , head[a] , c}; head[a] = cntEd;}void dfs1(int x , int p){ sz[x] = 1; fa[x] = p; dep[x] = dep[p] + 1; for(int i = head[x] ; i ; i = Ed[i].upEd) if(Ed[i].end != p){ len[Ed[i].end] = len[x] + Ed[i].w; dfs1(Ed[i].end , x); sz[x] += sz[Ed[i].end]; if(sz[Ed[i].end] > sz[son[x]]) son[x] = Ed[i].end; }}void dfs2(int x , int t){ top[x] = t; ind[dfn[x] = ++ts] = x; if(!son[x]) return; dfs2(son[x] , t); for(int i = head[x] ; i ; i = Ed[i].upEd) if(Ed[i].end != fa[x] && Ed[i].end != son[x]) dfs2(Ed[i].end , Ed[i].end);}namespace segTree{ line arr[_ << 2]; int mn[_ << 2] , pl[_ << 2] , pr[_ << 2];#define mid ((l + r) >> 1)#define lch (x << 1)#define rch (x << 1 | 1) void init(int x , int l , int r){ pl[x] = l; pr[x] = r; mn[x] = 123456789123456789ll; if(l != r){ init(lch , l , mid); init(rch , mid + 1, r); } } int calc(line A , int x){return A.k * x + A.b;} void up(int x){ if(pl[x] != pr[x]) mn[x] = min(min(mn[lch] , mn[rch]) , min(calc(arr[x] , len[ind[pl[x]]]) , calc(arr[x] , len[ind[pr[x]]]))); else mn[x] = min(calc(arr[x] , len[ind[pl[x]]]) , calc(arr[x] , len[ind[pr[x]]])); } void insert(int x , int l , int r , int L , int R , line now){ if(l >= L && r <= R){ if(arr[x].k == now.k) return (void)(arr[x] = arr[x].b < now.b ? arr[x] : now) , up(x); ld pos = sect(arr[x] , now); if(arr[x].k > now.k) swap(arr[x] , now); if(pos > len[ind[r]]) arr[x] = now; else if(!(pos < len[ind[l]])) if(pos >= len[ind[mid]]){ swap(arr[x] , now); if(l != r) insert(rch , mid + 1 , r , L , R , now); } else if(l != r) insert(lch , l , mid , L , R , now); return up(x); } if(mid >= L) insert(lch , l , mid , L , R , now); if(mid < R) insert(rch , mid + 1 , r , L , R , now); up(x); } int query(int x , int l , int r , int L , int R){ if(l >= L && r <= R) return mn[x]; int ans = 123456789123456789ll; if(mid >= L) ans = query(lch , l , mid , L , R); if(mid < R) ans = min(ans , query(rch , mid + 1 , r , L , R)); return min(ans , min(calc(arr[x] , len[ind[max(l , L)]]) , calc(arr[x] , len[ind[min(r , R)]]))); }}int LCA(int x , int y){ int tx = top[x] , ty = top[y]; while(tx != ty){ if(dep[tx] < dep[ty]){swap(tx , ty); swap(x , y);} x = fa[tx]; tx = top[x]; } return dfn[x] > dfn[y] ? y : x;}void modify(int x , int y , int a , int b){ int tx = top[x] , ty = top[y] , flgx = -1 , flgy = 1 , lx = 0 , ly = len[x] + len[y] - 2 * len[LCA(x , y)]; while(tx != ty){ if(dep[tx] < dep[ty]){swap(tx , ty); swap(flgx , flgy); swap(x , y); swap(lx , ly);} int _k = flgx * a , _b = lx * a + b - len[x] * _k; segTree::insert(1 , 1 , N , dfn[tx] , dfn[x] , line(_k , _b)); lx += -flgx * (len[x] - len[fa[tx]]); x = fa[tx]; tx = top[x]; } if(dep[x] < dep[y]){swap(flgx , flgy); swap(x , y); swap(lx , ly);} int _k = flgx * a , _b = lx * a + b - len[x] * _k; segTree::insert(1 , 1 , N , dfn[y] , dfn[x] , line(_k , _b));}int work(int x , int y){ int tx = top[x] , ty = top[y] , ans = 123456789123456789ll; while(tx != ty){ if(dep[tx] < dep[ty]){swap(tx , ty); swap(x , y);} ans = min(ans , segTree::query(1 , 1 , N , dfn[tx] , dfn[x])); x = fa[tx]; tx = top[x]; } return min(ans , segTree::query(1 , 1 , N , min(dfn[x] , dfn[y]) , max(dfn[x] , dfn[y])));}signed main(){#ifndef ONLINE_JUDGE freopen("in","r",stdin); freopen("out","w",stdout);#endif N = read(); M = read(); for(int i = 1 ; i < N ; ++i){ int a = read() , b = read() , c = read(); addEd(a , b , c); addEd(b , a , c); } dfs1(1 , 0); dfs2(1 , 1); segTree::init(1 , 1 , N); for(int i = 1 ; i <= M ; ++i) if(read() == 1){ int s = read() , t = read() , a = read() , b = read(); modify(s , t , a , b); } else{ int s = read() , t = read(); printf("%lld\n" , work(s , t)); } return 0;}