【BZOJ4515】[Sdoi2016]游戏
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 进行操作，输出一行一个数，表示他能够选择的最小的数字
Sample Input
3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3
Sample Output
123456789123456789
6
-106
6
-106
HINT
n≤100000，m≤100000，∣a∣≤10000,0<=w，|b|<=10^9
题解：很神的线段树~
一个操作相当于加入一条线段，一个询问相当于求一段区间的最小值。那么我们线段树的每个节点都要维护这些东西：左右端点的dis值，区间中最小的数，以及这段区间中最优的线段。但是如果又新来了一条线段呢？需要分类讨论了：
如果旧线段在左右端点的取值都比新线段优，则新线段显然没用；如果新线段在左右断电的取值都比旧线段有，则旧线段显然没用；否则呢？递归下去更新即可。
就这么完事了？嗯。时间复杂度？那就再来一个log呗，$O(nlog^3_n)$。（再来一个log你会更强）
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=100010;
typedef long long ll;
const ll inf=123456789123456789ll;
int n,m,cnt;
int to[maxn<<1],next[maxn<<1],val[maxn<<1],head[maxn],dep[maxn],siz[maxn],son[maxn],top[maxn],fa[maxn];
int p[maxn],q[maxn];
ll sa[maxn<<2],sb[maxn<<2],sl[maxn<<2],sr[maxn<<2],sn[maxn<<2],dis[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
inline void add(int a,int b,int c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void dfs1(int x)
{
siz[x]=1;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[x])
{
fa[to[i]]=x,dep[to[i]]=dep[x]+1,dis[to[i]]=dis[x]+val[i],dfs1(to[i]),siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(int x,int tp)
{
top[x]=tp,p[x]=++q[0],q[q[0]]=x;
if(son[x]) dfs2(son[x],tp);
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa[x]&&to[i]!=son[x]) dfs2(to[i],to[i]);
}
void build(int l,int r,int x)
{
sn[x]=sb[x]=inf;
if(l==r)
{
sl[x]=sr[x]=dis[q[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
sl[x]=sl[lson],sr[x]=sr[rson];
}
void updata(int l,int r,int x,int a,int b,ll c,ll d)
{
int mid=(l+r)>>1;
if(a<=l&&r<=b)
{
if(sl[x]*sa[x]+sb[x]>sl[x]*c+d&&sr[x]*sa[x]+sb[x]>sr[x]*c+d) sa[x]=c,sb[x]=d;
else if(sl[x]*sa[x]+sb[x]>sl[x]*c+d||sr[x]*sa[x]+sb[x]>sr[x]*c+d)
updata(l,mid,lson,a,b,c,d),updata(mid+1,r,rson,a,b,c,d);
sn[x]=min(sn[x],min(sl[x]*c+d,sr[x]*c+d));
if(l!=r) sn[x]=min(sn[x],min(sn[lson],sn[rson]));
return ;
}
if(a<=mid) updata(l,mid,lson,a,b,c,d);
if(b>mid) updata(mid+1,r,rson,a,b,c,d);
sn[x]=min(sn[x],min(sn[lson],sn[rson]));
return ;
}
ll query(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return sn[x];
ll ret=min(dis[q[a]]*sa[x]+sb[x],dis[q[b]]*sa[x]+sb[x]);
int mid=(l+r)>>1;
if(a<=mid) ret=min(ret,query(l,mid,lson,a,min(b,mid)));
if(b>mid) ret=min(ret,query(mid+1,r,rson,max(a,mid+1),b));
return ret;
}
inline int lca(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]]) x=fa[top[x]];
else y=fa[top[y]];
}
if(dep[x]>dep[y]) return y;
return x;
}
inline void modify()
{
int x=rd(),y=rd();
ll a=rd(),b=rd(),c=dis[x]*a+b,d=(dis[x]-2*dis[lca(x,y)])*a+b;
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]]) updata(1,n,1,p[top[x]],p[x],-a,c),x=fa[top[x]];
else updata(1,n,1,p[top[y]],p[y],a,d),y=fa[top[y]];
}
if(dep[x]<dep[y]) updata(1,n,1,p[x],p[y],a,d);
else updata(1,n,1,p[y],p[x],-a,c);
}
inline void ask()
{
int x=rd(),y=rd();
ll ret=inf;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ret=min(ret,query(1,n,1,p[top[x]],p[x])),x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ret=min(ret,query(1,n,1,p[x],p[y]));
printf("%lld\n",ret);
}
int main()
{
n=rd(),m=rd();
int i,a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),c=rd(),add(a,b,c),add(b,a,c);
dep[1]=1,dfs1(1),dfs2(1,1);
build(1,n,1);
for(i=1;i<=m;i++)
{
if(rd()==1) modify();
else ask();
}
return 0;
}//3 5 1 2 10 2 3 20 2 1 3 1 2 3 5 6 2 2 3 1 2 3 -5 -6 2 2 3