[USACO15DEC] Max Flow P

题目描述

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$ 个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到 $N$。所有隔间都被管道连通了。

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

输入格式

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

The next $N-1$ lines each contain two integers $x$ and $y$ ($x \ne 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.

第一行输入两个整数 $N$ 和 $K$。

接下来 $N-1$ 行每行输入两个整数 $x$ 和 $y$，其中 $x \ne y$。表示一根在牛棚 $x$ 和 $y$ 之间的管道。

接下来 $K$ 行每行两个整数 $s$ 和 $t$，描述一条从 $s$ 到 $t$ 的运输牛奶的路线。

输出格式

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

一个整数，表示压力最大的隔间的压力是多少。

样例 #1

样例输入 #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

提示

$2 \le N \le 5 \times 10^4,1 \le K \le 10^5$