4515: [Sdoi2016]游戏
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 351 Solved: 157
[Submit][Status][Discuss]
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
李超线段树？
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
const long long INF=123456789123456789LL;
int n,Q,cnt;
int fir[maxn],nxt[maxn<<],to[maxn<<],val[maxn<<];
int dep[maxn],fa[maxn],sz[maxn],son[maxn];
long long dis[maxn];
void addedge(int a,int b,int v){
nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;val[cnt]=v;
} void DFS(int x){
sz[x]=;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]){
fa[to[i]]=x;
dis[to[i]]=dis[x]+val[i];
dep[to[i]]=dep[x]+;
DFS(to[i]);
sz[x]+=sz[to[i]];
if(sz[son[x]]<sz[to[i]])
son[x]=to[i];
}
} int top[maxn],ID[maxn],rID[maxn],tot;
void DFS(int x,int tp){
ID[x]=++tot;rID[tot]=x;top[x]=tp;
if(son[x])DFS(son[x],tp);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=son[x]&&to[i]!=fa[x])
DFS(to[i],to[i]);
} int Lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
} struct Node{
long long a,b;
Node(long long a_=,long long b_=INF){
a=a_;b=b_;
}
long long Val(int x){
return a*dis[rID[x]]+b;
}
int CmP(int l,int r,Node a){
if(Val(l)<=a.Val(l)&&Val(r)<=a.Val(r))return ;
if(Val(l)>=a.Val(l)&&Val(r)>=a.Val(r))return -;
return ;
}
}F[maxn<<];
long long Min[maxn<<]; void Build(int x,int l,int r){
Min[x]=INF;
if(l==r)return;
Build(x<<,l,(l+r)>>);
Build(x<<|,((l+r)>>)+,r);
} void Update(int x,int l,int r,int a,int b,Node p){
int mid=(l+r)>>;
Min[x]=min(Min[x],min(p.Val(max(a,l)),p.Val(min(b,r))));
if(l>=a&&r<=b){
int tmp=p.CmP(l,r,F[x]);
if(tmp==)F[x]=p;
if(tmp!=)return; tmp=p.CmP(l,mid,F[x]);
if(tmp!=)Update(x<<,l,mid,a,b,F[x]); tmp=p.CmP(mid+,r,F[x]);
if(tmp!=)Update(x<<|,mid+,r,a,b,F[x]);
}
if(l==r)return;
if(mid>=a)Update(x<<,l,mid,a,b,p);
if(mid<b)Update(x<<|,mid+,r,a,b,p);
} void Modify(int x,int y,Node p){
while(top[x]!=top[y]){
Update(,,n,ID[top[x]],ID[x],p);
x=fa[top[x]];
}
Update(,,n,ID[y],ID[x],p);
} long long Query(int x,int l,int r,int a,int b){
if(l>=a&&r<=b)return Min[x];
int mid=(l+r)>>;
long long ret=min(F[x].Val(max(l,a)),F[x].Val(min(r,b)));
if(mid>=a)ret=min(ret,Query(x<<,l,mid,a,b));
if(mid<b)ret=min(ret,Query(x<<|,mid+,r,a,b));
return ret;
} long long Solve(int x,int y){
long long ret=INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret=min(ret,Query(,,n,ID[top[x]],ID[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
return min(ret,Query(,,n,ID[y],ID[x]));
} int main(){
#ifndef ONLINE_JUDGE
freopen("menci_game.in","r",stdin);
freopen("menci_game.out","w",stdout);
#endif
scanf("%d%d",&n,&Q);
for(int i=,x,y,w;i<n;i++){
scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);addedge(y,x,w);
} DFS();
DFS(,);
Build(,,n); int type,s,t,lca;
long long a,b;
while(Q--){
scanf("%d",&type);
if(type==){
scanf("%d%d%lld%lld",&s,&t,&a,&b);
lca=Lca(s,t);
Modify(s,lca,Node(-a,a*dis[s]+b));
Modify(t,lca,Node(a,a*(dis[s]-*dis[lca])+b));
}
else{
scanf("%d%d",&s,&t);
printf("%lld\n",Solve(s,t));
}
}
return ;
}