链接
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
",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;
}