4515: [Sdoi2016]游戏
Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 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=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') {if (ch=='-')f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } #define maxn 100100 struct EdgeNode{int next,to;long long len;}edge[maxn<<1]; 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]=1; 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]+1; 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<<2]; #define inf 123456789123456789LL void Build(int now,int l,int r) { tree[now].a=0; tree[now].b=tree[now].minn=inf; if (l==r) return; int mid=(l+r)>>1; Build(now<<1,l,mid); Build(now<<1|1,mid+1,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)>>1; if (R<=mid) return min(re,Query(now<<1,l,mid,L,R)); else if (L>mid) return min(re,Query(now<<1|1,mid+1,r,L,R)); else return min(re,min(Query(now<<1,l,mid,L,mid),Query(now<<1|1,mid+1,r,mid+1,R))); } void Change(int now,int l,int r,long long a,long long b) { int mid=(l+r)>>1,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<<1,l,mid,tree[now].a,tree[now].b); else Change(now<<1|1,mid+1,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<<1,l,mid,a,b); else Change(now<<1|1,mid+1,r,a,b); tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn,tree[now<<1|1].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)>>1; if (L<=mid) change(now<<1,l,mid,L,R,a,b); if (R>mid) change(now<<1|1,mid+1,r,L,R,a,b); tree[now].minn=min(tree[now].minn,min(tree[now<<1].minn,tree[now<<1|1].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(1,1,n,pl[top[x]],pl[x],-a,a*dis[s]+b); x=fa[top[x]]; } change(1,1,n,pl[lca],pl[x],-a,a*dis[s]+b); while (top[y]!=top[lca]) { change(1,1,n,pl[top[y]],pl[y],a,dis[s]*a-dis[lca]*2*a+b); y=fa[top[y]]; } if (y!=lca) change(1,1,n,pl[lca]+1,pl[y],a,dis[s]*a-dis[lca]*2*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(1,1,n,pl[top[x]],pl[x]),re); x=fa[top[x]]; } if (deep[x]>deep[y]) swap(x,y); re=min(Query(1,1,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=1; i<=n-1; i++) u=read(),v=read(),w=(long long)read(),insert(u,v,w); dfs_1(1); dfs_2(1,1); Build(1,1,n); while (m--) { int opt=read(); if (opt==1) { int s=read(),t=read();long long a=read(),b=read(); Solve_Insert(s,t,a,b); } if (opt==2) { int s=read(),t=read(); printf("%lld ",Solve_Query(s,t)); } } return 0; }
考场上，看到这个题，这不是裸树链剖分么，线段树维护半平面交，裸李超线段树啊，Clrs的模版上有哎，虽然我没写过，但是我知道大体的方法啊，然后开始码，码到最后连暴力都没打，然后愉快滚粗TAT/...