Description：

在一棵有边权的树上，进行两种操作：

$1$ 、选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$ ，若 $r$ 与 $ s $ 的距离是 $ dis$ ，那么在点 $ r $ 上添加的数字是 $ a\times dis+b$ 。

$2$ 、选择一条从 s 到 t 的路径，询问这条路径上最小的数字。

$1\le n \le 10^5$

Solution：

先树链剖分，然后发现每次是插入一条线段并询问区间最低点，用李超线段树维护：

如果覆盖，取下面那个；如果交叉，取中点较靠上的那条线段，并将线段分成两半，将较低的那部分下放到子节点。

维护一个区间最小值，每次询问时直接查询即可，注意由于维护了区间最小值，所以和 $HEOI\ segment$ 不同的是每一次对根节点的操作都要和两个儿子节点取 $min$ 。

还发现树边有边权，于是记下每个点的深度，由于树剖时更新的部分一定是树上的一条连续的链，于是计算一下得到一个以 $deep[i]$ 为下标的一次函数把这个函数插进去即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

typedef long long ll;

struct edge

{

	int to,nxt;

	ll v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

ll deep[MAXN];

int top[MAXN],siz[MAXN],son[MAXN],dep[MAXN],fa[MAXN],rank[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			deep[e[i].to] = deep[k] + e[i].v;

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rank[k] = ++tot;

	th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

struct line

{

	ll k,b;

	ll f(ll x){return k * x + b;}

};

struct node

{

	int lc,rc;

	line l;

	ll minn;

	node(){l.b = minn = 123456789123456789ll;l.k = 0ll;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

bool cover(line a,line b,ll l,ll r){if(a.f(l) >= b.f(l) && a.f(r) >= b.f(r))return true;else return false;}

void add(int rt,int L,int R,line k,int l,int r)

{

	if(L <= l && r <= R)

	{

		if(cover(t[rt].l,k,deep[th[l]],deep[th[r]])){t[rt].l = k;t[rt].minn = min(t[rt].minn,min(k.f(deep[th[l]]),k.f(deep[th[r]])));return;}

		if(cover(k,t[rt].l,deep[th[l]],deep[th[r]]))return;

		if(k.f(deep[th[mid]]) < t[rt].l.f(deep[th[mid]]))

		{

			swap(k,t[rt].l);

			t[rt].minn = min(t[rt].minn,min(t[rt].l.f(deep[th[l]]),t[rt].l.f(deep[th[r]])));

		}

		if(l == r)

		{

			t[rt].minn = min(t[rt].minn,t[rt].l.f(deep[th[mid]]));

			return;

		}

		if(k.f(deep[th[l]]) < t[rt].l.f(deep[th[l]]))add(t[rt].lc,L,R,k,l,mid);

		if(k.f(deep[th[r]]) < t[rt].l.f(deep[th[r]]))add(t[rt].rc,L,R,k,mid + 1,r);

	}

	else

	{

		if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

		if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	}

	t[rt].minn = min(t[rt].minn,min(t[t[rt].lc].minn,t[t[rt].rc].minn));

	t[rt].minn = min(t[rt].minn,min(t[rt].l.f(deep[th[l]]),t[rt].l.f(deep[th[r]])));

	return;

}

void change(int s,int t,ll a,ll b)

{

	int lca = LCA(s,t);

	int ss = s,tt = t;

	while(top[ss] != top[lca])

	{

		add(root,rank[top[ss]],rank[ss],(line){-a,b + a * deep[s]},1,n);

		ss = fa[top[ss]];

	}

	while(top[tt] != top[lca])

	{

		add(root,rank[top[tt]],rank[tt],(line){a,b + a * (deep[s] - 2 * deep[lca])},1,n);

		tt = fa[top[tt]];

	}

	if(ss != lca)add(root,rank[tt],rank[ss],(line){-a,b + a * deep[s]},1,n);

	else add(root,rank[ss],rank[tt],(line){a,b + a * (deep[s] - 2 * deep[lca])},1,n);

	return;

}

ll query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)

	{

		return t[rt].minn;

	}

	ll res = 0x3f3f3f3f3f3f3f3f;

	if(L <= mid)res = min(res,query(t[rt].lc,L,R,l,mid));

	if(R > mid)res = min(res,query(t[rt].rc,L,R,mid + 1,r));

	res = min(res,min(t[rt].l.f(deep[th[max(l,L)]]),t[rt].l.f(deep[th[min(r,R)]])));

	return res;

}

ll ask(int s,int t)

{

	ll res = 0x3f3f3f3f3f3f3f3f;

	while(top[s] != top[t])

	{

		if(dep[top[s]] < dep[top[t]])swap(s,t);

		res = min(res,query(root,rank[top[s]],rank[s],1,n));

		s = fa[top[s]];

	}

	if(dep[s] > dep[t])swap(s,t);

	res = min(res,query(root,rank[s],rank[t],1,n));

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	int u,v;

	ll w;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%lld",&u,&v,&w);

		add(u,v,w);

	}

	dfs1(1,1);

	dfs2(1,1);

	build(root,1,n);

	int type,s,t;

	ll a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&type);

		if(type == 1)

		{

			scanf("%d%d%lld%lld",&s,&t,&a,&b);

			change(s,t,a,b);

		}

		else

		{

			scanf("%d%d",&s,&t);

			printf("%lld\n",ask(s,t));

		}

	}

	return 0;

}