BZOJ4515: [Sdoi2016]游戏

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
typedef long long ll;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
	if(head==tail) {
		int l=fread(buffer,1,BufferSize,stdin);
		tail=(head=buffer)+l;
	}
	return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;
    return x*f;
}
const int maxn=100010;
const ll inf=123456789123456789ll;
ll ans,minv[maxn<<2],val[maxn],dist[maxn];
int n,m,first[maxn],next[maxn<<1],to[maxn<<1],dis[maxn<<1],e;
void AddEdge(int w,int v,int u) {
	to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;
	to[++e]=u;dis[e]=w;next[e]=first[v];first[v]=e;
}
int fa[maxn],dep[maxn],son[maxn],siz[maxn];
void dfs(int x) {
	dep[x]=dep[fa[x]]+1;siz[x]=1;
	ren if(to[i]!=fa[x]) {
		fa[to[i]]=x;dist[to[i]]=dist[x]+dis[i];
		dfs(to[i]);siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[to[son[x]]]) son[x]=i;
	}
}
int top[maxn],pos[maxn],cnt;
void build(int x,int tp) {
	top[x]=tp;pos[x]=++cnt;val[cnt]=dist[x];
	if(son[x]) build(to[son[x]],tp);
	ren if(to[i]!=fa[x]&&i!=son[x]) build(to[i],to[i]);
}
int setv[maxn<<2];
struct Line {
	int k;ll b;
	ll f(ll x) {return x*k+b;}
}A[maxn<<2];
void query(int o,int l,int r,int ql,int qr) {
	if(setv[o]) ans=min(ans,min(A[o].f(val[max(ql,l)]),A[o].f(val[min(qr,r)])));
	if(ql<=l&&r<=qr) ans=min(ans,minv[o]);
	else {
		int mid=l+r>>1,lc=o<<1,rc=lc|1;
		if(ql<=mid) query(lc,l,mid,ql,qr);
		if(qr>mid) query(rc,mid+1,r,ql,qr);
	}
}
void maintain(int o,int l,int r) {
	int lc=o<<1,rc=lc|1;
	if(l<r) minv[o]=min(minv[lc],minv[rc]);
	if(setv[o]) minv[o]=min(minv[o],min(A[o].f(val[l]),A[o].f(val[r])));
}
void cover(int o,int l,int r,Line x) {
	if(!setv[o]) setv[o]=1,A[o]=x;
	else if(l==r) {
		if(A[o].f(val[l])>x.f(val[l])) A[o]=x;
	}
	else {
		int mid=l+r>>1,lc=o<<1,rc=lc|1;
		ll fl=A[o].f(val[l]),fr=A[o].f(val[r]);
		ll gl=x.f(val[l]),gr=x.f(val[r]);
		if(fl>=gl&&fr>=gr) A[o]=x;
		else if(fl<=gl&&fr<=gr) return;
		else {
			if(gl<fl) {
				if(A[o].f(val[mid])<=x.f(val[mid])) cover(lc,l,mid,x);
				else cover(rc,mid+1,r,A[o]),A[o]=x;
			}
			if(gr<fr) {
				if(A[o].f(val[mid+1])<=x.f(val[mid+1])) cover(rc,mid+1,r,x);
				else cover(lc,l,mid,A[o]),A[o]=x;
			}
		}
	}
	maintain(o,l,r);
}
void update(int o,int l,int r,int ql,int qr,Line x) {
	if(ql<=l&&r<=qr) cover(o,l,r,x);
	else {
		int mid=l+r>>1,lc=o<<1,rc=lc|1;
		if(ql<=mid) update(lc,l,mid,ql,qr,x);
		if(qr>mid) update(rc,mid+1,r,ql,qr,x);
		maintain(o,l,r);
	}
}
int query(int x,int y,int tp) {
	int f1=top[x],f2=top[y];
	while(f1!=f2) {
		if(dep[f1]<dep[f2]) swap(f1,f2),swap(x,y);
		if(tp) query(1,1,n,pos[f1],pos[x]);
		x=fa[f1];f1=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(tp) query(1,1,n,pos[x],pos[y]);
	return x;
}
void update(int x,int z,int k,ll b) {
	int f=top[x];
	while(f!=top[z]) {
		update(1,1,n,pos[f],pos[x],(Line){k,b});
		x=fa[f];f=top[x];
	}
	update(1,1,n,pos[z],pos[x],(Line){k,b});
}
int main() {
	n=read();m=read();
	rep(i,2,n) AddEdge(read(),read(),read());
	dfs(1);build(1,1);
	rep(i,1,n*4) minv[i]=inf;
	rep(i,1,m) {
		int tp=read(),x=read(),y=read();
		if(tp==2) {
			ans=inf;query(x,y,1);
			printf("%lld\n",ans);
		}
		else {
			int a=read(),b=read();
			int z=query(x,y,0);
			update(x,z,-a,b+dist[x]*a);
			update(y,z,a,b+(dist[x]-2*dist[z])*a);
		}
	}
	return 0;
}