4515: [Sdoi2016]游戏
Time Limit: 40 Sec Memory Limit: 256 MB
Submit:
304 Solved: 129
[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
Source
Solution
仍旧是李超线段树维护半平面交，唯一不同的是这里有了一个距离的定义
只需要在比较的时候带入端点和终点的距离即可，至于李超线段树，此处安利一个非常好的文章：戳这里
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long read()
{
long long x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define maxn 100100
struct EdgeNode{int next,to;long long len;}edge[maxn<<];
int head[maxn],cnt;
void add(int u,int v,long long w)
{
cnt++;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].len=w;
}
void insert(int u,int v,long long w) {add(u,v,w); add(v,u,w);}
int n,m;
//--------------------------------------------------------------------------------------------------------
int pl[maxn],sz,pr[maxn],size[maxn],deep[maxn],son[maxn],top[maxn],fa[maxn];long long dis[maxn],pre[maxn];
void dfs_1(int x)
{
size[x]=;
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa[x])
{
fa[edge[i].to]=x;
deep[edge[i].to]=deep[x]+;
dis[edge[i].to]=dis[x]+edge[i].len;
dfs_1(edge[i].to);
if (size[son[x]]<size[edge[i].to]) son[x]=edge[i].to;
size[x]+=size[edge[i].to];
}
}
void dfs_2(int x,int chain)
{
pl[x]=++sz; pre[sz]=dis[x]; top[x]=chain;
if (son[x]) dfs_2(son[x],chain);
for (int i=head[x]; i; i=edge[i].next)
if (edge[i].to!=fa[x] && edge[i].to!=son[x])
dfs_2(edge[i].to,edge[i].to);
pr[x]=sz;
}
int LCA(int x,int y)
{
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
return x;
}
//--------------------------------------------------------------------------------------------------------
long long f(long long x,long long k,long long b) {return k*x+b;}
struct TreeNode{long long a,b,minn;}tree[maxn<<];
#define inf 123456789123456789LL
void Build(int now,int l,int r)
{
tree[now].a=; tree[now].b=tree[now].minn=inf;
if (l==r) return;
int mid=(l+r)>>;
Build(now<<,l,mid); Build(now<<|,mid+,r);
}
long long Query(int now,int l,int r,int L,int R)
{
long long re=min(f(pre[L],tree[now].a,tree[now].b),f(pre[R],tree[now].a,tree[now].b));
if (l==L && r==R) return min(re,tree[now].minn);
int mid=(l+r)>>;
if (R<=mid) return min(re,Query(now<<,l,mid,L,R));
else if (L>mid) return min(re,Query(now<<|,mid+,r,L,R));
else return min(re,min(Query(now<<,l,mid,L,mid),Query(now<<|,mid+,r,mid+,R)));
}
void Change(int now,int l,int r,long long a,long long b)
{
int mid=(l+r)>>,fl,fr,fm;
fl=(f(pre[l],tree[now].a,tree[now].b)>f(pre[l],a,b));
fr=(f(pre[r],tree[now].a,tree[now].b)>f(pre[r],a,b));
fm=(f(pre[mid],tree[now].a,tree[now].b)>f(pre[mid],a,b));
if (fl&fr&fm)
{
tree[now].a=a;tree[now].b=b;tree[now].minn=min(tree[now].minn,min(f(pre[l],a,b),f(pre[r],a,b)));
return;
}
if (!(fl|fr|fm)) return;
if (fm)
{
if (fr) Change(now<<,l,mid,tree[now].a,tree[now].b);
else Change(now<<|,mid+,r,tree[now].a,tree[now].b);
tree[now].a=a;tree[now].b=b;tree[now].minn=min(tree[now].minn,min(f(pre[l],a,b),f(pre[r],a,b)));
}
if (!fm)
if (!fr) Change(now<<,l,mid,a,b);
else Change(now<<|,mid+,r,a,b);
tree[now].minn=min(tree[now].minn,min(tree[now<<].minn,tree[now<<|].minn));
}
void change(int now,int l,int r,int L,int R,long long a,long long b)
{
if (L<=l && R>=r) {Change(now,l,r,a,b); return;}
int mid=(l+r)>>;
if (L<=mid) change(now<<,l,mid,L,R,a,b);
if (R>mid) change(now<<|,mid+,r,L,R,a,b);
tree[now].minn=min(tree[now].minn,min(tree[now<<].minn,tree[now<<|].minn));
}
//--------------------------------------------------------------------------------------------------------
void Solve_Insert(int s,int t,long long a,long long b)
{
int lca=LCA(s,t); int x=s,y=t;
while (top[x]!=top[lca])
{
change(,,n,pl[top[x]],pl[x],-a,a*dis[s]+b);
x=fa[top[x]];
}
change(,,n,pl[lca],pl[x],-a,a*dis[s]+b);
while (top[y]!=top[lca])
{
change(,,n,pl[top[y]],pl[y],a,dis[s]*a-dis[lca]**a+b);
y=fa[top[y]];
}
if (y!=lca) change(,,n,pl[lca]+,pl[y],a,dis[s]*a-dis[lca]**a+b);
}
long long Solve_Query(int s,int t)
{
int x=s,y=t; long long re=inf;
while (top[x]!=top[y])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
re=min(Query(,,n,pl[top[x]],pl[x]),re);
x=fa[top[x]];
}
if (deep[x]>deep[y]) swap(x,y);
re=min(Query(,,n,pl[x],pl[y]),re);
return re;
}
//--------------------------------------------------------------------------------------------------------
int main()
{
// freopen("menci_game.in","r",stdin);
// freopen("menci_game.out","w",stdout);
n=read();m=read(); long long w;
for (int u,v,i=; i<=n-; i++)
u=read(),v=read(),w=(long long)read(),insert(u,v,w);
dfs_1(); dfs_2(,); Build(,,n);
while (m--)
{
int opt=read();
if (opt==)
{
int s=read(),t=read();long long a=read(),b=read();
Solve_Insert(s,t,a,b);
}
if (opt==)
{
int s=read(),t=read();
printf("%lld\n",Solve_Query(s,t));
}
}
return ;
}
考场上，看到这个题，这不是裸树链剖分么，线段树维护半平面交，裸李超线段树啊，Clrs的模版上有哎，虽然我没写过，但是我知道大体的方法啊，然后开始码，码到最后连暴力都没打，然后愉快滚粗TAT/...