description
一棵树，支持链上插入一次函数，询问链上最大值。
(n,mle10^5)
sol
题面已经简化成这样了那就是裸的超哥线段树了吧。注意这里就算下标是离散的超哥线段树还是可以做的。
超哥线段树具体实现原理这里就不讲了因为我也不会。
复杂度(O(nlog^3n))，显得有点假，但是能过。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll long long
const int N = 1e5+5;
const ll inf = 123456789123456789ll;
int n,m,to[N<<1],nxt[N<<1],ww[N<<1],head[N],cnt,fa[N],dep[N],sz[N],son[N],top[N],dfn[N],id[N];
ll dis[N],mn[N<<2];
struct line{
ll k,b;
ll f(ll x){return k*x+b;}
}t[N<<2];
void link(int u,int v,int w){
to[++cnt]=v;nxt[cnt]=head[u];ww[cnt]=w;head[u]=cnt;
}
void dfs1(int u,int f){
fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
for (int e=head[u];e;e=nxt[e])
if (to[e]!=f){
dis[to[e]]=dis[u]+ww[e];
dfs1(to[e],u),sz[u]+=sz[to[e]];
if (sz[to[e]]>sz[son[u]]) son[u]=to[e];
}
}
void dfs2(int u,int up){
top[u]=up;id[dfn[u]=++cnt]=u;
if (son[u]) dfs2(son[u],up);
for (int e=head[u];e;e=nxt[e])
if (to[e]!=fa[u]&&to[e]!=son[u])
dfs2(to[e],to[e]);
}
int lca(int u,int v){
while (top[u]^top[v]){
if (dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
void build(int x,int l,int r){
t[x].b=mn[x]=inf;
if (l==r) return;int mid=l+r>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void pushup(int x,int l,int r){
if (l<r) mn[x]=min(mn[x<<1],mn[x<<1|1]);
mn[x]=min(mn[x],min(t[x].f(dis[id[l]]),t[x].f(dis[id[r]])));
}
void update(int x,int l,int r,line tmp){
int mid=l+r>>1;
if (tmp.f(dis[id[mid]])<t[x].f(dis[id[mid]])) swap(t[x],tmp);
if (l==r) {pushup(x,l,r);return;}
if (tmp.k>t[x].k) update(x<<1,l,mid,tmp);
else update(x<<1|1,mid+1,r,tmp);
pushup(x,l,r);
}
void modify(int x,int l,int r,int ql,int qr,line tmp){
if (l>=ql&&r<=qr) {update(x,l,r,tmp);return;}
int mid=l+r>>1;
if (ql<=mid) modify(x<<1,l,mid,ql,qr,tmp);
if (qr>mid) modify(x<<1|1,mid+1,r,ql,qr,tmp);
pushup(x,l,r);
}
ll query(int x,int l,int r,int ql,int qr){
if (l>=ql&&r<=qr) return mn[x];
int mid=l+r>>1;ll res=min(t[x].f(dis[id[ql]]),t[x].f(dis[id[qr]]));
if (qr<=mid) return min(res,query(x<<1,l,mid,ql,qr));
if (ql>mid) return min(res,query(x<<1|1,mid+1,r,ql,qr));
return min(res,min(query(x<<1,l,mid,ql,mid),query(x<<1|1,mid+1,r,mid+1,qr)));
}
int main(){
n=gi();m=gi();
for (int i=1;i<n;++i){
int u=gi(),v=gi(),w=gi();
link(u,v,w);link(v,u,w);
}
dfs1(1,0);cnt=0;dfs2(1,1);build(1,1,n);
while (m--){
int op=gi(),u=gi(),v=gi();
if (op&1){
ll a=gi(),b=gi();int gg=lca(u,v);
line tmp=(line){a,(dis[u]-dis[gg]*2)*a+b};
while (top[v]^top[gg])
modify(1,1,n,dfn[top[v]],dfn[v],tmp),v=fa[top[v]];
modify(1,1,n,dfn[gg],dfn[v],tmp);
tmp=(line){-a,dis[u]*a+b};
while (top[u]^top[gg])
modify(1,1,n,dfn[top[u]],dfn[u],tmp),u=fa[top[u]];
modify(1,1,n,dfn[gg],dfn[u],tmp);
}else{
ll res=inf;
while (top[u]^top[v]){
if (dep[top[u]]<dep[top[v]]) swap(u,v);
res=min(res,query(1,1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if (dep[u]>dep[v]) swap(u,v);
res=min(res,query(1,1,n,dfn[u],dfn[v]));
printf("%lld
",res);
}
}
return 0;
}