【SDOI2016】bzoj4515 游戏

本文主要是介绍【SDOI2016】bzoj4515 游戏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description Alice 和 Bob 在玩一个游戏。 游戏在一棵有 n 个点的树上进行。最初，每个点上都只有一个数字，那个数字是
123456789123456789。 有时，Alice 会选择一条从 s 到 t
的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 r， 若 r 与 s 的距离是 dis，那么 Alice 在点 r
上添加的数字是 a×dis+b。有时，Bob 会选择一条从 s 到 t 的路径。 他需要先从这条路径上选择一个点，再从那个点上选择一个数字。
Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。 Input 第一行两个数字
n、m，表示树的点数和进行的操作数。 接下来 n−1 行，每行三个数字 u、v、w，表示树上有一条连接 u、v 的边，长度是 w。 接下来
m 行。每行第一个数字是 1 或 2。 若第一个数是 1，表示 Alice 进行操作，接下来四个数字 s、t、a、b。 若第一个数是
2，表示 Bob 进行操作，接下来四个数字 s、t。 Output

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字

首先考虑序列上的问题，操作包括插入线段和询问区间最低点。用线段树来维护，线段树的每个节点存放一条线段和最优值。插入新线段的时候，先和普通的线段树区间修改一样找到要修改的位置，如果当前线段完全优直接换掉，完全劣直接舍去。否则根据图像可以发现，这两个线段一定有一个覆盖了一半多的区间【也就是在中点更优的那个】。把它放在这个节点，另外一个递归进入对应子树修改。在这个过程中顺便维护最优值。询问的时候就和普通的线段树一样了，但是注意这里不是简单的区间合并，在每个节点都要用当前线段更新答案。
放在树上也一样，只需要剖分一下。对于修改$(s,t,a,b)$在LCA点$u$处拆成两条链，分别是$(s,u):y=-a*dis[x]+a*dis[s]+b$和$(t,u):y=a*dis[x]+a*dis[s]-2a*dis[u]+b$，其中$dis[i]$表示$i$到根的距离。把$dis[x]$看成线段的横坐标就行了。因为边权是正的，一段链上的$dis$值一定是递增的。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const LL oo=123456789123456789LL;
const int maxn=100010;
int rd()
{int x=0,f=1;char c=getchar();while (c<'0'||c>'9'){if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
struct Segment
{LL k,b;LL cal(LL x){return k*x+b;}
}low[2000010];
int fir[maxn],ne[2*maxn],to[2*maxn],w[2*maxn],
size[maxn],pos[maxn],top[maxn],fa[maxn][20],son[maxn],dep[maxn],
n,q,clo,lim;
LL dis[maxn],d2[maxn],mn[2000010];
int cmp(Segment s1,Segment s2,LL x)
{return s1.cal(x)<s2.cal(x);
}
void add(int num,int u,int v,int x)
{ne[num]=fir[u];fir[u]=num;to[num]=v;w[num]=x;
}
void dfs1(int u)
{int v;size[u]=1;for (int i=fir[u];i;i=ne[i])if ((v=to[i])!=fa[u][0]){fa[v][0]=u;dep[v]=dep[u]+1;dis[v]=dis[u]+w[i];dfs1(v);size[u]+=size[v];if (!son[u]||size[v]>size[son[u]]) son[u]=v;}
}
void dfs2(int u)
{int v;pos[u]=++clo;if (son[u]){top[son[u]]=top[u];dfs2(son[u]);}for (int i=fir[u];i;i=ne[i])if ((v=to[i])!=fa[u][0]&&v!=son[u]){top[v]=v;dfs2(v);}
}
int lca(int u,int v)
{if (dep[u]<dep[v]) swap(u,v);for (int k=lim;k>=0;k--)if (dep[u]-(1<<k)>=dep[v])u=fa[u][k];if (u==v) return u;for (int k=lim;k>=0;k--)if (fa[u][k]!=fa[v][k]){u=fa[u][k];v=fa[v][k];}return fa[u][0];
}
void build(int p,int L,int R)
{low[p]=(Segment){0,oo};mn[p]=oo;if (L<R){int mid=L+R>>1;build(p<<1,L,mid);build(p<<1|1,mid+1,R);}
}
void init()
{int u,v,x;n=rd();q=rd();for (int i=1;i<n;i++){u=rd();v=rd();x=rd();add(i<<1,u,v,x);add(i<<1|1,v,u,x);}dep[1]=1;dfs1(1);top[1]=1;dfs2(1);for (int i=1;i<=n;i++) d2[pos[i]]=dis[i];for (int k=1;(1<<k)<=n;k++) lim=k;for (int k=1;k<=lim;k++)for (int i=1;i<=n;i++)fa[i][k]=fa[fa[i][k-1]][k-1];build(1,1,n);
}
void down(int p,int L,int R,Segment s1)
{mn[p]=min(mn[p],min(s1.cal(d2[L]),s1.cal(d2[R])));if (L==R){if (cmp(s1,low[p],d2[L])) low[p]=s1;return;}int mid=L+R>>1,cl,cr,cm;cl=cmp(s1,low[p],d2[L]);cr=cmp(s1,low[p],d2[R]);cm=cmp(s1,low[p],d2[mid]);if (cl==cr){if (cl) low[p]=s1;}else{if (cm){if (cl) down(p<<1|1,mid+1,R,low[p]);else down(p<<1,L,mid,low[p]);low[p]=s1;}else{if (cl) down(p<<1,L,mid,s1);else down(p<<1|1,mid+1,R,s1);}}
}
void modify(int p,int L,int R,int l,int r,Segment s1)
{mn[p]=min(mn[p],min(s1.cal(d2[max(L,l)]),s1.cal(d2[min(R,r)])));if (l<=L&&R<=r){down(p,L,R,s1);return;}int mid=L+R>>1;if (l<=mid) modify(p<<1,L,mid,l,r,s1);if (r>mid) modify(p<<1|1,mid+1,R,l,r,s1);
}
void Modify(int v,int u,Segment s1)
{while (top[v]!=top[u]){modify(1,1,n,pos[top[v]],pos[v],s1);v=fa[top[v]][0];}modify(1,1,n,pos[u],pos[v],s1);
}
LL query(int p,int L,int R,int l,int r)
{if (l<=L&&R<=r) return mn[p];int mid=L+R>>1;LL ans=oo;if (l<=mid) ans=min(ans,query(p<<1,L,mid,l,r));if (r>mid) ans=min(ans,query(p<<1|1,mid+1,R,l,r));ans=min(ans,low[p].cal(d2[max(l,L)]));ans=min(ans,low[p].cal(d2[min(r,R)]));return ans;
}
LL Query(int u,int v)
{LL ret=oo;while (top[u]!=top[v]){if (dep[top[u]]<dep[top[v]]) swap(u,v);ret=min(ret,query(1,1,n,pos[top[u]],pos[u]));u=fa[top[u]][0];}if (dep[u]<dep[v]) swap(u,v);ret=min(ret,query(1,1,n,pos[v],pos[u]));return ret;
}
void solve()
{int opt,s,t,a,b,u;opt=rd();if (opt==1){s=rd();t=rd();a=rd();b=rd();u=lca(s,t);Modify(s,u,(Segment){-a,a*dis[s]+b});Modify(t,u,(Segment){a,a*dis[s]-2*a*dis[u]+b});}else{s=rd();t=rd();printf("%lld\n",Query(s,t));}
}
int main()
{/*freopen("menci_game.in","r",stdin);freopen("menci_game.out","w",stdout);*/init();while (q--) solve();
}

这篇关于【SDOI2016】bzoj4515 游戏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---