YbtOJ 634「左偏树」转移石子
YbtOJ 634「左偏树」转移石子
题目链接：YbtOJ #634
小 A 有一棵 n 个点的无根树，节点标号为 1\sim n。其中第 i 条边长度为 l_i。
在标号为 i 的点上原本有 x_i 颗石子。
石子只能沿着树边转移，且对于一条边 (u,v,l)，将一颗石子从 u 移到 v 或从 v 移到 u 的代价都是 l。
小 A 希望在若干次转移之后使得标号为 i 的点上至少有 y_i 颗石子，求最小的转移代价。
1\le n\le2.5\times10^5，\sum y_i\le\sum x_i\le10^6，1\leq l\leq 10^6。
Tutorial
显然一个点上原有的 \min{x_i,y_i} 颗石子没有必要移动。
因此 x_i > y_ix_i-y_i 颗石子，x_i < y_iy_i-x_i 颗石子。
然后就可以暴力建图：
- 从超级源向能够给出石子的点连边，容量为需要给出的石子数，费用为 0。
- 从需要接收石子的点向超级汇连边，容量为需要接收的石子数，费用为 -INF（这样使得接收石子的点肯定会接收满）。
- 从需要给出石子的点向需要接收石子的点之间连边，容量为 INF，费用为距离。
然后考虑模拟费用流来优化。在每个点处理它不同子树间的流动。
假设有输出点 x 和接收点 y，当前点（\operatorname{LCA}）为 z，它们之间的路径长度就是 d_x+d_y-2d_z，匹配费用就是 d_x+d_y-2d_z-INF。
由于当前点确定时 -2d_z 为定值，因此规定输出点的权值 A_x=d_x，接收点的权值 B_y=d_y-INF，然后分别开一个小根堆，每次取出各自的堆顶尝试更新答案即可。（更新答案的条件：A_x+B_y-2d_z < 0
但我们还要考虑退流，如果我们想让输出点 x 能换成和另一个接收点匹配，相当于新建一个权值为 2d_z-B_y 的输出点 x’，这两个输出点权值相加刚好消得只剩 A_x，除去了原本的接收点的贡献。同理，想让接收点 y 能换成和另一个输出点匹配，相当于新建一个权值为 2d_z-A_x 的接收点 y’。
因为这里的堆需要合并，写个左偏树即可。
也就是反悔贪心。
Solution
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2.5e5+10;Cn LL inf=1e13;
int n,fir[N],nxt[N<<1],son[N<<1],w[N<<1],tot;LL d[N],Ans;
#define PA pair<int,int>
#define MP make_pair
#define fi first
#define se second
PA a[N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
class Tree{
private:
int cnt;struct node{int l,r,d;LL v;}T[N*40];
public:
int rt[N];
I int M(RI x,RI y){
if(!x!y) return x+y;if(T[x].v>T[y].v) swap(x,y);
T[x].r=M(T[x].r,y);if(T[T[x].l].d<T[T[x].r].d) swap(T[x].l,T[x].r);
return T[x].d=T[T[x].r].d+1,x;
}
I void P(int& x,LL v){T[++cnt]=(node){0,0,0,v},x=M(x,cnt);}
I void O(int& x){x=M(T[x].l,T[x].r);}
I LL top(CI x){return T[rt[x]].v;}
I void pop(CI x){O(rt[x]);}
}p,q;
I void DFS(CI x,CI fa){
W(a[x].se--) p.P(p.rt[x],d[x]);W(a[x].fi--) q.P(q.rt[x],d[x]-inf);
RI i;LL tp,tq,t;for(i=fir[x];i;i=nxt[i]) to^fa&&(d[to]=d[x]+w[i],DFS(to,x),p.rt[x]=p.M(p.rt[x],p.rt[to]),q.rt[x]=q.M(q.rt[x],q.rt[to]),0);
W(p.rt[x]&&q.rt[x]&&(t=(tp=p.top(x))+(tq=q.top(x))-2*d[x])<0)
Ans+=t,p.pop(x),q.pop(x),p.P(p.rt[x],tp-t),q.P(q.rt[x],tq-t);
}
int main(){
freopen("rock.in","r",stdin),freopen("rock.out","w",stdout);
RI i,x,y,z,X=0;for(read(n),i=1;i<n;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);
for(i=1;i<=n;i++) read(a[i].fi,a[i].se),x=min(a[i].fi,a[i].se),a[i].fi-=x,a[i].se-=x,X+=a[i].se;
return DFS(1,0),writeln(Ans+X*inf),0;
}腾讯云开发者
