记录编号	390030	评测结果	AAWWWWWWWWWWWWWWWWWW
题目名称	[SDOI 2016 Round1] 游戏	最终得分	10
用户昵称	FoolMike	是否通过	未通过
代码语言	C++	运行时间	30.895 s
提交时间	2017-04-01 15:40:30	内存使用	233.00 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll inf=123456789123456789ll;
struct edge{int f,t,l;}w[N];
int n,m,next[N],head[N];
void add(int f,int t,int l){
	static int cnt=0;
	w[++cnt]=(edge){f,t,l};
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],dfn[N],link[N],size[N],big[N];
ll h[N],dep[N];
void dfs(int x){
	size[x]=1;
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		int v=w[i].t;
		fa[v]=x;
		h[v]=h[x]+w[i].l;
		dfs(v);
		size[x]+=size[v];
		if (size[v]>size[big[x]]) big[x]=v;
	}
}
void po(int x){
	static int cnt=0;
	dfn[x]=++cnt;
	link[x]=(cnt==dfn[fa[x]]+1?link[fa[x]]:x);
	if (!big[x]) return;
	po(big[x]);
	for (int i=head[x];i;i=next[i])
		if (w[i].t!=big[x]&&w[i].t!=fa[x]) po(w[i].t); 
}
int lca(int x,int y){
	for (;link[x]!=link[y];x=fa[link[x]])
		if (dfn[link[x]]<dfn[link[y]]) swap(x,y);
	return dfn[x]<dfn[y]?x:y;
}
struct pt{
	ll x,y;
	pt(ll X=0,ll Y=0){x=X;y=Y;}
	pt operator - (const pt a)const{return pt(x-a.x,y-a.y);}
	ll operator * (const pt a)const{return x*a.y-y*a.x;}
};
struct half_plane{
private:
	vector<pt> q;
	int tl;
	bool check(pt &x,pt &y,pt &z){
		return (y-x)*(z-x)>0;
	}
	void insert(pt &x){
		for (;tl>=0&&check(q[tl-1],q[tl],x);q.pop_back(),tl--);
		q.push_back(x);tl++;
	}
public:
	void init(){q.clear();tl=-1;}
	void ins(pt x){
		if (tl>0&&q[tl].x==x.x){
			if (q[tl].y>x.y) q.pop_back(),tl--,insert(x);
			return;
		}
		insert(x);
	}
	ll query(ll x){
		if (tl<0) return inf;
		int l=0,r=tl;
		while (l^r){
			int mid=(l+r)>>1;
			if (x*(q[mid].x-q[mid+1].x)<q[mid+1].y-q[mid].y) r=mid;else l=mid+1;
		}
		return x*q[l].x+q[l].y;
	}
};
int L,R;pt v;
struct segment_tree{
	half_plane a[N];
	ll Min[N];
	segment_tree(){
		for (int i=1;i<N;i++)
			a[i].init(),Min[i]=inf;
	}
	#define lc x<<1
	#define rc x<<1|1
	void clear(int x,int l,int r){
		a[x].init();Min[x]=inf;
		if (l>=L&&r<=R) return;
		int mid=(l+r)>>1;
		if (L<=mid) clear(lc,l,mid);
		if (R>mid) clear(rc,mid+1,r);
	}
	void add(int x,int l,int r){
		if (l>=L&&r<=R){
			a[x].ins(v);
			Min[x]=min(Min[x],a[x].query(dep[l]));
			Min[x]=min(Min[x],a[x].query(dep[r]));
			return;
		}
		int mid=(l+r)>>1;
		if (L<=mid) add(lc,l,mid);
		if (R>mid) add(rc,mid+1,r);
		Min[x]=min(Min[lc],Min[rc]);
	}
	ll query(int x,int l,int r){
		if (l>=L&&r<=R) return Min[x];
		int mid=(l+r)>>1;
		ll ans=min(a[x].query(dep[min(r,R)]),a[x].query(dep[max(l,L)]));
		if (L<=mid) ans=min(ans,query(lc,l,mid));
		if (R>mid) ans=min(ans,query(rc,mid+1,r));
		return ans;
	}
}T;
const int M=4e6+10;
ll ans[M];
struct opt{int tp,l,r;ll a,b;}Q[M];int id;
void modify(int s,int t){
	ll a,b;
	scanf("%lld%lld",&a,&b);
	int LCA=lca(s,t);
	b+=a*h[s];
	for (;link[s]!=link[LCA];s=fa[link[s]])
		Q[++id]=(opt){1,dfn[link[s]],dfn[s],-a,b};
	Q[++id]=(opt){1,dfn[LCA],dfn[s],-a,b};
	b-=2*a*h[LCA];
	for (;link[t]!=link[LCA];t=fa[link[t]])
		Q[++id]=(opt){1,dfn[link[t]],dfn[t],a,b};
	Q[++id]=(opt){1,dfn[LCA],dfn[t],a,b};
}
ll query(int x,int y){
	ll ans=inf;
	for (;link[x]!=link[y];x=fa[link[x]]){
		if (dfn[link[x]]<dfn[link[y]]) swap(x,y);
		L=dfn[link[x]];R=dfn[x];
		ans=min(ans,T.query(1,1,n));
	}
	if (dfn[x]>dfn[y]) swap(x,y);
	L=dfn[x];R=dfn[y];
	return min(ans,T.query(1,1,n));
}
int q[M];
void cdq(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	for (int i=l;i<=mid;i++){
		opt &now=Q[q[i]];
		if (now.tp==1){
			L=now.l;R=now.r;v=pt(now.a,now.b);
			T.add(1,1,n);
		}
	}
	for (int i=mid+1;i<=r;i++)
		if (!Q[i].tp) ans[i]=min(ans[i],query(Q[i].l,Q[i].r));
	for (int i=l;i<=mid;i++){
		opt &now=Q[q[i]];
		if (now.tp==1) L=now.l,R=now.r,T.clear(1,1,n);
	}
	static int a[N];
	int i=l,j=mid+1,p=l;
	while (i<=mid&&j<=r) a[p++]=Q[q[i]].a>Q[q[j]].a?q[i++]:q[j++];
	for (;i<=mid;a[p++]=q[i++]);
	for (;j<=r;a[p++]=q[j++]);
	for (i=l;i<=r;i++) q[i]=a[i];
}
int main()
{
	freopen("menci_game.in","r",stdin);
	freopen("menci_game.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		add(u,v,l);add(v,u,l);
	}
	fa[1]=1;dfs(1);po(1);
	for (int i=1;i<=n;i++) dep[dfn[i]]=h[i];
	while (m--){
		int tp,x,y;
		scanf("%d%d%d",&tp,&x,&y);
		if (tp==1) modify(x,y);else Q[++id]=(opt){0,x,y,0ll,0ll};
	}
	for (int i=1;i<=id;i++) q[i]=i,ans[i]=inf;
	//for (int i=1;i<=id;i++)
	//	printf("%d %d->%d a=%lld b=%lld\n",Q[i].tp,Q[i].l,Q[i].r,Q[i].a,Q[i].b);
	cdq(1,id);
	for (int i=1;i<=id;i++)
		if (!Q[i].tp) printf("%lld\n",ans[i]);
	return 0;
}