本文主要是介绍bzoj4515 [Sdoi2016]游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
树链剖分和李超线段树共同食用。
与之前的单点查询李超线段树不同，这道题要求区间查询，而李超线段树的本质是一种标记永久化，所以我们要在查询时判断区间左右进行计算。
两点间距离可能非常大，一定要开long long！（这个错花了我一下午和半个晚上才找出来）
CODE：
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const ll INF=123456789123456789ll;
struct edge
{int nxt,to,dis;
}a[N<<1];
struct line
{ll k,b,num;bool flag;line(){}line(ll kk,ll bb):k(kk),b(bb){num=INF,flag=1;}ll y(ll x){return flag?k*x+b:INF;}
}t[N<<2];
int head[N],deep[N],size[N],f[N],son[N],top[N],pos[N],wh[N];
ll dis[N];
int n,m,opt,x,y,z,w,num,tot;
inline void swap(int &a,int &b){a^=b,b^=a,a^=b;}
inline void add(int x,int y,int z)
{a[++num].nxt=head[x],a[num].to=y,a[num].dis=z,head[x]=num;a[++num].nxt=head[y],a[num].to=x,a[num].dis=z,head[y]=num;
}
void dfs(int now,int fa,int depth,ll dist)
{f[now]=fa,deep[now]=depth;size[now]=1;dis[now]=dist;int tmp=0;for(int i=head[now];i;i=a[i].nxt)if(a[i].to!=fa){dfs(a[i].to,now,depth+1,dist+a[i].dis);size[now]+=size[a[i].to];if(size[a[i].to]>tmp) tmp=size[a[i].to],son[now]=a[i].to;}
}
void dfs2(int now,int high)
{top[now]=high,pos[now]=++tot,wh[tot]=now;if(son[now]) dfs2(son[now],high);for(int i=head[now];i;i=a[i].nxt)if(a[i].to!=f[now]&&a[i].to!=son[now]) dfs2(a[i].to,a[i].to);
}
void build(int l,int r,int now)
{t[now].num=INF;if(l==r) return;int mid=(l+r)>>1;build(l,mid,now<<1);build(mid+1,r,now<<1|1);
}
inline int LCA(int x,int y)
{while(top[x]!=top[y])if(deep[top[x]]>deep[top[y]]) x=f[top[x]];else y=f[top[y]];return deep[x]<deep[y]?x:y;
}
inline void update(int l,int r,int now)
{if(l==r) t[now].num=INF;else t[now].num=min(t[now<<1].num,t[now<<1|1].num);if(t[now].flag) t[now].num=min(t[now].num,min(dis[wh[l]]*t[now].k,dis[wh[r]]*t[now].k)+t[now].b);
}
inline ll point(line a,line b){return (b.b-a.b)/(a.k-b.k);}
void Add(int L,int R,int l,int r,int now,line tmp)
{if(L<=l&&r<=R){if(!t[now].flag){t[now]=tmp,update(l,r,now);return;}ll nowl=t[now].y(dis[wh[l]]),nowr=t[now].y(dis[wh[r]]),tmpl=tmp.y(dis[wh[l]]),tmpr=tmp.y(dis[wh[r]]);if(nowl<=tmpl&&nowr<=tmpr) return;if(nowl>tmpl&&nowr>tmpr){t[now]=tmp;return update(l,r,now);}int mid=(l+r)>>1;ll pos=point(t[now],tmp);if(pos<=dis[wh[mid]])if(tmp.k<t[now].k) Add(L,R,l,mid,now<<1,t[now]),t[now]=tmp;else Add(L,R,l,mid,now<<1,tmp);else if(tmp.k<t[now].k) Add(L,R,mid+1,r,now<<1|1,tmp);else Add(L,R,mid+1,r,now<<1|1,t[now]),t[now]=tmp;return update(l,r,now);}int mid=(l+r)>>1;if(L<=mid) Add(L,R,l,mid,now<<1,tmp);if(R>mid) Add(L,R,mid+1,r,now<<1|1,tmp);update(l,r,now);
}
ll ask(int L,int R,int l,int r,int now)
{if(L<=l&&r<=R) return t[now].num;int mid=(l+r)>>1;ll ans=INF;if(t[now].flag) ans=min(dis[wh[max(L,l)]]*t[now].k,dis[wh[min(R,r)]]*t[now].k)+t[now].b;if(L<=mid) ans=min(ans,ask(L,R,l,mid,now<<1));if(R>mid) ans=min(ans,ask(L,R,mid+1,r,now<<1|1));return ans;
}
void addpath(int x,int y,line tmp)
{int L,R;if(top[x]==top[y]){L=min(pos[x],pos[y]);R=max(pos[x],pos[y]);return Add(L,R,1,n,1,tmp);}if(deep[top[x]]<deep[top[y]]) swap(x,y);L=min(pos[x],pos[top[x]]);R=max(pos[x],pos[top[x]]);Add(L,R,1,n,1,tmp);addpath(y,f[top[x]],tmp);
}
inline void insert(int x,int y,int z,int w)
{int lca=LCA(x,y);ll tmp=1ll*z*dis[x]+1ll*w;addpath(x,lca,line(-z,tmp));addpath(lca,y,line(z,tmp-(dis[lca]<<1)*z));
}
ll askpath(int x,int y)
{int L,R;if(top[x]==top[y]){L=min(pos[x],pos[y]);R=max(pos[x],pos[y]);return ask(L,R,1,n,1);}if(deep[top[x]]<deep[top[y]]) swap(x,y);L=min(pos[x],pos[top[x]]);R=max(pos[x],pos[top[x]]);ll ans=ask(L,R,1,n,1);return min(ans,askpath(y,f[top[x]]));
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),add(x,y,z);dfs(1,0,1,0),dfs2(1,1),build(1,n,1);while(m--){scanf("%d",&opt);if(opt==1) scanf("%d%d%d%d",&x,&y,&z,&w),insert(x,y,z,w);else scanf("%d%d",&x,&y),printf("%lld\n",askpath(x,y));}return 0;
}这篇关于bzoj4515 [Sdoi2016]游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
