洛谷P3128 [USACO15DEC]最大流Max Flow [树链剖分]

题目描述

Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ( $2 leq N leq 50,000$ ), conveniently numbered $1 ldots N$ . Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ( $1 leq K leq 100,000$ ). For the $i$ th such pair, you are told two stalls $s_i$ and $t_i$ , endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i$ to $t_i$ , then it counts as being pumped through the endpoint stalls $s_i$ and

$t_i$ , as well as through every stall along the path between them.

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入输出格式

输入格式：

The first line of the input contains $N$ and $K$ .

The next $N-1$ lines each contain two integers $x$ and $y$ ( $x e y$ ) describing a pipe

between stalls $x$ and $y$ .

The next $K$ lines each contain two integers $s$ and $t$ describing the endpoint

stalls of a path through which milk is being pumped.

输出格式：

An integer specifying the maximum amount of milk pumped through any stall in the

barn.

输入输出样例

输入样例#1：

输出样例#1：

虽然名叫Max Flow，但是和网络流半点关系没有。

正解似乎是利用树剖求LCA，然后按照差分权值。（树上差分，结点权值等于其子树的差分累计结果）

然而并没有多想就写了树剖+线段树暴力维护链修改和区间最大值……

1825ms龟速水过。

  1 /*by SilverN*/
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<cmath>
  7 #include<vector>
  8 using namespace std;
  9 const int mxn=200010;
 10 int read(){
 11     int x=0,f=1;char ch=getchar();
 12     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 14     return x*f;
 15 }
 16 int n,k;
 17 struct edge{
 18     int v,nxt;
 19 }e[mxn<<1];
 20 int hd[mxn],mct=0;
 21 void add_edge(int u,int v){
 22     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;
 23 }
 24 struct node{
 25     int f,son;
 26     int top,size,dep;
 27     int w,e;
 28 }tr[mxn];
 29 struct segtree{
 30     int mk,mx;
 31 }st[mxn<<2];
 32 int sz=0;
 33 void DFS1(int u){
 34     tr[u].size=1;
 35     tr[u].son=0;
 36     for(int i=hd[u];i;i=e[i].nxt){
 37         int v=e[i].v;
 38         if(v==tr[u].f)continue;
 39         tr[v].f=u;
 40         tr[v].dep=tr[u].dep+1;
 41         DFS1(v);
 42         tr[u].size+=tr[v].size;
 43         if(tr[v].size>tr[tr[u].son].size)tr[u].son=v;
 44     }
 45     return;
 46 }
 47 void DFS2(int u,int top){
 48     tr[u].top=top;
 49     tr[u].w=++sz;
 50     if(tr[u].son){
 51         DFS2(tr[u].son,top);
 52         for(int i=hd[u];i;i=e[i].nxt){
 53             int v=e[i].v;
 54             if(v!=tr[u].f && v!=tr[u].son)
 55                 DFS2(v,v);
 56         }
 57     }
 58     tr[u].e=sz;
 59     return;
 60 }
 61 void pushdown(int l,int r,int rt){
 62     if(l==r)return;
 63     int mid=(l+r)>>1;
 64     st[rt<<1].mk+=st[rt].mk;
 65     st[rt<<1|1].mk+=st[rt].mk;
 66     st[rt<<1].mx+=st[rt].mk;
 67     st[rt<<1|1].mx+=st[rt].mk;
 68     st[rt].mk=0;
 69     return;
 70 }
 71 void add(int L,int R,int v,int l,int r,int rt){
 72     if(L<=l && r<=R){
 73         st[rt].mk+=v;
 74         st[rt].mx+=v;
 75         return;
 76     }
 77     if(st[rt].mk)pushdown(l,r,rt);
 78     int mid=(l+r)>>1;
 79     if(L<=mid)add(L,R,v,l,mid,rt<<1);
 80     if(R>mid)add(L,R,v,mid+1,r,rt<<1|1);
 81     st[rt].mx=max(st[rt<<1].mx,st[rt<<1|1].mx);
 82     return;
 83 }
 84 int qmx(int L,int R,int l,int r,int rt){
 85     if(L<=l && r<=R)return st[rt].mx;
 86     if(st[rt].mk)pushdown(l,r,rt);
 87     int mid=(l+r)/2;
 88     int res=-1e9;
 89     if(L<=mid)res=max(res,qmx(L,R,l,mid,rt<<1));
 90     if(R>mid)res=max(res,qmx(L,R,mid+1,r,rt<<1|1));
 91     return res;
 92 }
 93 void qadd(int x,int y){
 94     while(tr[x].top!=tr[y].top){
 95         if(tr[tr[x].top].dep<tr[tr[y].top].dep)swap(x,y);
 96         add(tr[tr[x].top].w,tr[x].w,1,1,n,1);
 97         x=tr[tr[x].top].f;
 98     }
 99     if(tr[x].w>tr[y].w)swap(x,y);
100     add(tr[x].w,tr[y].w,1,1,n,1);
101     return;
102 }
103 int main(){
104     n=read();k=read();
105     int i,j,u,v,x,y;
106     for(i=1;i<n;i++){
107         u=read();v=read();
108         add_edge(u,v);
109         add_edge(v,u);
110     }
111     DFS1(1);
112     DFS2(1,1);
113     for(i=1;i<=k;i++){
114 /*
115         for(i=1;i<=sz;i++){
116             printf("%d ",qmx(tr[i].w,tr[i].w,1,n,1));
117         }
118         printf("
");*/
119         x=read();y=read();
120         qadd(x,y);
121     }
122     printf("%d
",st[1].mx);
123     return 0;
124 }