C120 树剖+李超树 P4069 [SDOI2016] 游戏

视频链接：

 

 

 

 

D12 Luogu P3384【模板】轻重链剖分/树链剖分 - 董晓 - 博客园 (cnblogs.com) 

Luogu P4069 [SDOI2016] 游戏

// 树剖+李超树 O(nlognlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
#define ls u<<1
#define rs u<<1|1
const int N=100005;
const ll INF=123456789123456789;int tot,head[N],to[N<<1],ne[N<<1],w[N<<1];
void add(int a,int b,int c){to[++tot]=b;w[tot]=c;ne[tot]=head[a];head[a]=tot;
}
int fa[N],son[N],dep[N],siz[N]; //树剖数组
int top[N],dfn[N],old[N],tim;
ll dis[N]; //到树根的距离void dfs1(int u,int f){fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;for(int i=head[u];i;i=ne[i]){int v=to[i];if(v==f) continue;dis[v]=dis[u]+w[i];dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;}
}
void dfs2(int u,int tp){top[u]=tp,dfn[u]=++tim,old[tim]=u;if(son[u]) dfs2(son[u],tp);for(int i=head[u];i;i=ne[i]){int v=to[i];if(v==fa[u]||v==son[u])continue;dfs2(v,v);}
}
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;
}int n,m,cnt;
struct line{ //线段int k; ll b;line(){k=0,b=INF;}line(int x,ll y){k=x,b=y;}
}p[N<<1];struct tree{ //李超树int id;    //优势线段的编号ll mi;     //最小值tree(){mi=INF;}
}tr[N<<3];   //因访问叶子节点的儿子，故开8倍空间

ll Y(int id,ll x){ //求Y值return p[id].k*x+p[id].b;
}
void pushup(int u,int l,int r){ //上传ll ans=min(Y(tr[u].id,dis[old[l]]),Y(tr[u].id,dis[old[r]]));tr[u].mi=min(ans,min(tr[ls].mi,tr[rs].mi));
}
void change(int u,int l,int r,int L,int R,int id){ //区修int mid=(l+r)>>1;if(L<=l&&r<=R){if(Y(id,dis[old[mid]])<Y(tr[u].id,dis[old[mid]])) swap(id,tr[u].id);if(Y(id,dis[old[l]])<Y(tr[u].id,dis[old[l]])) change(ls,l,mid,L,R,id);if(Y(id,dis[old[r]])<Y(tr[u].id,dis[old[r]])) change(rs,mid+1,r,L,R,id);pushup(u,l,r);return;}if(L<=mid) change(ls,l,mid,L,R,id);if(R>mid) change(rs,mid+1,r,L,R,id);pushup(u,l,r);
}
void treechange(int u,int v,int id){ //树修while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);change(1,1,n,dfn[top[u]],dfn[u],id);u=fa[top[u]]; //爬链
  }if(dep[u]>dep[v]) swap(u,v);change(1,1,n,dfn[u],dfn[v],id); //最后一段
}
ll query(int u,int l,int r,int L,int R){ //区查if(L<=l&&r<=R) return tr[u].mi;int mid=(l+r)>>1;ll ans=min(Y(tr[u].id,dis[old[max(l,L)]]),Y(tr[u].id,dis[old[min(r,R)]]));if(L<=mid) ans=min(ans,query(ls,l,mid,L,R));if(R>mid) ans=min(ans,query(rs,mid+1,r,L,R));return ans;
}
ll treequery(int u,int v){ //树查ll ans=INF;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);ans=min(ans,query(1,1,n,dfn[top[u]],dfn[u]));u=fa[top[u]]; //爬链
  }if(dep[u]>dep[v]) swap(u,v);return min(ans,query(1,1,n,dfn[u],dfn[v]));
}
int main(){scanf("%d%d",&n,&m);for(int i=1,u,v,w; i<=n-1; i++)scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);dfs1(1,0),dfs2(1,1);for(int i=1,op,s,t; i<=m; i++){scanf("%d%d%d",&op,&s,&t);if(op==1){int a,b,lca;scanf("%d%d",&a,&b); lca=LCA(s,t);p[++cnt]=line(-a,a*dis[s]+b);treechange(s,lca,cnt);p[++cnt]=line(a,a*(dis[s]-2*dis[lca])+b);treechange(lca,t,cnt);}else printf("%lld\n",treequery(s,t));}
}