[SDOI2016]游戏

[SDOI2016]游戏

思路：
树剖+李超线段树
李超线段树模板题，把对一条链的操作变成李超线段树上一段区间的操作。维护李超就像普通的维护直线一样，但是每个区间加个标记，代表在自己下面的区间直线所出现的最小值，这样就保证了复杂度。
把一条链拆成从$s$到$lca$，从$lca$到$t$的两个线段。

普普通通的AC吧；

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int n,m;
struct node{
	int e,next;
	ll w;
}z[200005];
int len=0;
int head[100006];
ll dis[100006];
int siz[100006],dep[100006],fa[100006],top[100006];
int id[100006],dfn[100006],son[100006],cnt=0;
void add(int a,int b,ll k){
	z[len].e=b;
	z[len].w=k;
	z[len].next=head[a];
	head[a]=len++;
}
void dfs1(int x,int pre)
{
	fa[x]=pre;dep[x]=dep[pre]+1;
	siz[x]=1;
	for(int i=head[x];i!=-1;i=z[i].next)
	{
		int y=z[i].e;
		if(y==pre)continue;
		dis[y]=dis[x]+z[i].w;
		dfs1(y,x);
		siz[x]+=siz[y];
		if(siz[y]>=siz[son[x]])son[x]=y;
	}
}

void dfs2(int x,int pre)
{
	if(son[pre]==x)top[x]=top[pre];
	else top[x]=x;
	id[x]=++cnt;
	dfn[cnt]=x;
	if(son[x]!=0)dfs2(son[x],x);
	for(int i=head[x];i!=-1;i=z[i].next)
	{
		int y=z[i].e;
		if(y==pre)continue;if(son[x]==y)continue;
		dfs2(y,x);
	}
}
ll tb[400005],tk[400005];
int vis[400005];
ll minn[400005];

void build(int p,int l,int r){
	minn[p]=123456789123456789;
	if(l==r)return;
	int mid=l+r>>1;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
}
void update(int p,int l,int r,int x,int y,ll b,ll k){
	if(x<=l&&r<=y){
		ll l3=dis[dfn[l]],r3=dis[dfn[r]];
		ll l1=tk[p]*l3+tb[p],r1=tk[p]*r3+tb[p]
				,l2=k*l3+b,r2=k*r3+b;
		if(vis[p]==0){
			tb[p]=b;tk[p]=k;vis[p]=1;
			minn[p]=min(minn[p],min(l2,r2));
			return ;
		}
		if(l1<l2&&r1<r2)return;
		if(l1>=l2&&r1>=r2){
			tk[p]=k;tb[p]=b;
			minn[p]=min(minn[p],min(l2,r2));
			return;
		}
		ll mid=l+r>>1;
		mid=dis[dfn[mid]];
		double xx=1.0*(b-tb[p])/(tk[p]-k);
		if(l1>=l2){
			int mi=l+r>>1;
			if(xx>=mid)update(2*p+1,mi+1,r,x,y,tb[p],tk[p]),tb[p]=b,tk[p]=k;
			else update(2*p,l,mi,x,y,b,k);
		}else{
			int mi=l+r>>1;
			if(xx>=mid)update(2*p+1,mi+1,r,x,y,b,k);
			else update(2*p,l,mi,x,y,tb[p],tk[p]),tb[p]=b,tk[p]=k;
		}
		minn[p]=min(minn[p],min(l2,r2));
		minn[p]=min(minn[p],min(minn[2*p],minn[2*p+1]));
		return ;
	}
	int mid=l+r>>1;
	if(x<=mid)update(2*p,l,mid,x,y,b,k);
	if(mid<y)update(2*p+1,mid+1,r,x,y,b,k);
	minn[p]=min(minn[p],min(minn[2*p],minn[2*p+1]));
}
ll query(int p,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return minn[p];
	}
	ll ans=123456789123456789;
	int mid=l+r>>1;
	if(vis[p]){
		ll dis1=dis[dfn[max(l,x)]];
		ll dis2=dis[dfn[min(r,y)]];
		ans=min(tk[p]*dis1+tb[p],tk[p]*dis2+tb[p]);
	}
	if(x<=mid)ans=min(ans,query(2*p,l,mid,x,y));
	if(mid<y)ans=min(ans,query(2*p+1,mid+1,r,x,y));
	return ans;
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]])swap(x,y);
		y=fa[top[y]];
	}
	if(dep[x]>dep[y])swap(x,y);
	return x;
}
void lca1(int x,int y,ll a,ll b){
	int p=lca(x,y);
	ll len=dis[x]-dis[p];
	ll ss=dis[x];
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			update(1,1,n,id[top[x]],id[x],b+a*ss,-a);
			x=fa[top[x]];
		}else{
			update(1,1,n,id[top[y]],id[y],b-a*dis[p]+a*len,a);
			y=fa[top[y]];
		}
	}
	if(dep[x]>dep[y]){
		update(1,1,n,id[y],id[x],b+a*ss,-a);
	}else{
		update(1,1,n,id[x],id[y],b-a*dis[p]+a*len,a);
	}
}
ll query1(int x,int y){
	ll ans=123456789123456789;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			ans=min(ans,query(1,1,n,id[top[x]],id[x]));
			x=fa[top[x]];
		}
		else {
			ans=min(ans,query(1,1,n,id[top[y]],id[y]));
			y=fa[top[y]];
		}
	}
	if(dep[x]>dep[y]){
		ans=min(ans,query(1,1,n,id[y],id[x]));
	}else{
		ans=min(ans,query(1,1,n,id[x],id[y]));
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	for(int i=1;i<n;i++){
		int a,b;
		ll c;
		scanf("%d%d%lld",&a,&b,&c);
		add(a,b,c);add(b,a,c);
	}
	dfs1(1,0);dfs2(1,0);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op;
		int s,t;
		ll a,b;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%lld%lld",&s,&t,&a,&b);
			lca1(s,t,a,b);
		}else{
			scanf("%d%d",&s,&t);
			printf("%lld\n",query1(s,t));
		}
	}
	return 0;
}
/*
3 100
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
*/