洛谷——P3128 [USACO15DEC]最大流Max Flow

时间:2021-12-22 22:44:45

https://www.luogu.org/problem/show?pid=3128

题目描述

Farmer John has installed a new system of 洛谷——P3128 [USACO15DEC]最大流Max Flow pipes to transport milk between the 洛谷——P3128 [USACO15DEC]最大流Max Flow stalls in his barn (洛谷——P3128 [USACO15DEC]最大流Max Flow), conveniently numbered 洛谷——P3128 [USACO15DEC]最大流Max Flow. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between 洛谷——P3128 [USACO15DEC]最大流Max Flow pairs of stalls (洛谷——P3128 [USACO15DEC]最大流Max Flow). For the 洛谷——P3128 [USACO15DEC]最大流Max Flowth such pair, you are told two stalls 洛谷——P3128 [USACO15DEC]最大流Max Flow and 洛谷——P3128 [USACO15DEC]最大流Max Flow, 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 洛谷——P3128 [USACO15DEC]最大流Max Flow 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 洛谷——P3128 [USACO15DEC]最大流Max Flow to 洛谷——P3128 [USACO15DEC]最大流Max Flow, then it counts as being pumped through the endpoint stalls 洛谷——P3128 [USACO15DEC]最大流Max Flow and

洛谷——P3128 [USACO15DEC]最大流Max Flow, 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 洛谷——P3128 [USACO15DEC]最大流Max Flow and 洛谷——P3128 [USACO15DEC]最大流Max Flow.

The next 洛谷——P3128 [USACO15DEC]最大流Max Flow lines each contain two integers 洛谷——P3128 [USACO15DEC]最大流Max Flow and 洛谷——P3128 [USACO15DEC]最大流Max Flow (洛谷——P3128 [USACO15DEC]最大流Max Flow) describing a pipe

between stalls 洛谷——P3128 [USACO15DEC]最大流Max Flow and 洛谷——P3128 [USACO15DEC]最大流Max Flow.

The next 洛谷——P3128 [USACO15DEC]最大流Max Flow lines each contain two integers 洛谷——P3128 [USACO15DEC]最大流Max Flow and 洛谷——P3128 [USACO15DEC]最大流Max Flow 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:
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
输出样例#1:
9

树剖+树上查分

 #include <algorithm>
#include <cstdio> using namespace std; const int N(+);
int n,k,u,v; int head[N],sumedge;
struct Edge
{
int v,next;
Edge(int v=,int next=):
v(v),next(next){}
}edge[N<<];
void ins(int u,int v)
{
edge[++sumedge]=Edge(v,head[u]);
head[u]=sumedge;
} int size[N],deep[N],dad[N],top[N];
void DFS(int x)
{
size[x]=; deep[x]=deep[dad[x]]+;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(dad[x]==v) continue;
dad[v]=x; DFS(v); size[x]+=size[v];
}
}
void DFS_(int x)
{
int t=; if(!top[x]) top[x]=x;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(dad[x]!=v&&size[t]<size[v]) t=v;
}
if(t) top[t]=top[x],DFS_(t);
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(dad[x]!=v&&t!=v) DFS_(v);
}
}
int LCA(int x,int y)
{
for(;top[x]!=top[y];x=dad[top[x]])
if(deep[top[x]]<deep[top[y]]) swap(x,y);
return deep[x]<deep[y]?x:y;
} int ans,val[N];
void DFS_val(int x)
{
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(dad[x]==v) continue;
DFS_val(v); val[x]+=val[v];
}
ans=max(val[x],ans);
} int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
ins(u,v); ins(v,u);
}
DFS(); DFS_();
for(;k--;)
{
scanf("%d%d",&u,&v);
val[u]++; val[v]++;
int lca=LCA(u,v);
val[lca]--;val[dad[lca]]--;
}
DFS_val();
printf("%d",ans);
return ;
}