链接

https://www.luogu.org/problemnew/show/P4069

思路

树剖+超哥线段树

我已经自毙了，自闭了！！！！

update

上次抄了没认真看，这次考试又自毙了

是一个细节的处理上一次没处理

代码

#include <bits/stdc++.h>

#define ll long long

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

const ll inf=123456789123456789LL;

const ll N=5e5+7;

ll read() {

	ll x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

ll n,m;

struct edge {

	ll v,nxt,q;

}e[N<<1];

ll head[N<<1],tot;

void add(ll u,ll v,ll q) {

	e[++tot].v=v;

	e[tot].q=q;

	e[tot].nxt=head[u];

	head[u]=tot;

}

ll fa[N],dep[N],son[N],siz[N];

ll dis[N];

void dfs1(ll u,ll f) {

	dep[u]=dep[f]+1;

	siz[u]=1;

	fa[u]=f;

	for(ll i=head[u];i;i=e[i].nxt) {

		ll v=e[i].v;

		if(v==f) continue;

		dis[v]=dis[u]+(ll)e[i].q;

		dfs1(v,u);

		siz[u]+=siz[v];

		if(siz[son[u]]<siz[v]) son[u]=v;

	}

}

ll idx[N],top[N],js;

ll xxx[N];

void dfs2(ll u,ll topf) {

	idx[u]=++js;

	xxx[js]=u;

	top[u]=topf;

	if(!son[u]) return;

	dfs2(son[u],topf);

	for(ll i=head[u];i;i=e[i].nxt) {

		ll v=e[i].v;

		if(!idx[v]) dfs2(v,v);

	}

}

struct node {

	ll l,r;

	ll a,b,mi;

}tr[N<<2];

void build(ll l,ll r,ll rt) {

	tr[rt].l=l,tr[rt].r=r;

	tr[rt].mi=tr[rt].b=inf;

	if(l==r) return;

	ll mid=(l+r)>>1;

	build(l,mid,ls);

	build(mid+1,r,rs);

}

ll f(ll a,ll b,ll x) {

	return a*dis[xxx[x]]+b;

}

#define f_l f(tr[rt].a,tr[rt].b,tr[rt].l)

#define f_r f(tr[rt].a,tr[rt].b,tr[rt].r)

void pushup(ll rt) {

	tr[rt].mi=min(tr[rt].mi,min(tr[ls].mi,tr[rs].mi));

	tr[rt].mi=min(tr[rt].mi,min(f_l,f_r));

}

void modify(ll L,ll R,ll a,ll b,ll rt) {

	if(L<=tr[rt].l&&tr[rt].r<=R) {

		if(f_l<=f(a,b,tr[rt].l)&&f_r<=f(a,b,tr[rt].r)) return;

		if(f_l>f(a,b,tr[rt].l)&&f_r>f(a,b,tr[rt].r)) {

			tr[rt].a=a;

			tr[rt].b=b;

			tr[rt].mi=min(tr[rt].mi,min(f_l,f_r));

			return;

		}

		ll mid=(tr[rt].l+tr[rt].r)>>1;

		if(tr[rt].a<=a) {

			if(f(tr[rt].a,tr[rt].b,mid)>=f(a,b,mid)) {

				swap(tr[rt].a,a);

				swap(tr[rt].b,b);

				modify(L,R,a,b,rs);

			} else modify(L,R,a,b,ls);

		} else {

			if(f(tr[rt].a,tr[rt].b,mid)>=f(a,b,mid)) {

				swap(tr[rt].a,a);

				swap(tr[rt].b,b);

				modify(L,R,a,b,ls);

			} else modify(L,R,a,b,rs);

		}

		 tr[rt].mi= min(min(tr[ls].mi, tr[rs].mi), min(f_l,f_r));

		// pushup(rt);

		return;

	}

	ll mid=(tr[rt].l+tr[rt].r)>>1;

	if(L<=mid) modify(L,R,a,b,ls);

	if(R>mid) modify(L,R,a,b,rs);

	pushup(rt);

}

ll query(ll L,ll R,ll rt) {

	if(L<=tr[rt].l&&tr[rt].r<=R) {

		return tr[rt].mi;

	}

	ll mid=(tr[rt].l+tr[rt].r)>>1;

	ll ans=inf;

	ans=min(ans,min(f(tr[rt].a,tr[rt].b,max(L,tr[rt].l)),f(tr[rt].a,tr[rt].b,min(tr[rt].r,R))));

	if(L<=mid) ans=min(ans,query(L,R,ls));

	if(R>mid) ans=min(ans,query(L,R,rs));

	return ans;

}

ll lca(ll x,ll y) {

	while(top[x]!=top[y]) {

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		x=fa[top[x]];

	}

	if(dep[x]>dep[y]) swap(x,y);

	return x;

}

void C(ll x,ll y,ll a,ll b) {

	while(top[x]!=top[y]) {

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		modify(idx[top[x]],idx[x],a,b,1);

		x=fa[top[x]];

	}

	if(dep[x]>dep[y]) swap(x,y);

	modify(idx[x],idx[y],a,b,1);

}

void Q(ll x,ll y) {

	ll ans=inf;

	while(top[x]!=top[y]) {

		if(dep[top[x]] < dep[top[y]]) swap(x,y);

		ans=min(ans,query(idx[top[x]],idx[x],1));

		x=fa[top[x]];

	}

	if(dep[x]>dep[y]) swap(x,y);

	ans=min(ans,query(idx[x],idx[y],1));

	printf("%lld\n",ans);

}

int main() {

	n=read(),m=read();

	for(ll i=1;i<n;++i) {

		ll x=read(),y=read(),z=read();

		add(x,y,z);

		add(y,x,z);

	}

	dfs1(1,0);

	dfs2(1,1);

	build(1,n,1);

	while(m--) {

		ll opt=read();

		if(opt==1) {

			ll s=read(),t=read();

			ll A=read(),B=read();

			ll dsr=lca(s,t);

			C(s,dsr,(ll)-A,1LL*dis[s]*A+B);

			C(dsr,t,(ll)A,1LL*dis[s]*A-2LL*A*dis[dsr]+B);

		} else {

			ll s=read(),t=read();

			Q(s,t);

		}

	}

	return 0;

}