YbtOJ 634「左偏树」转移石子

(Updated: )
oi
, , ,

题目链接：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_i$ 的情况可以视作能够给出 $x_i-y_i$ 颗石子，$x_i < y_i$ 的情况可以视作需要接收 $y_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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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;
}