[USACO15DEC] Max Flow P

题意翻译

### 题目描述 Farmer John 在他的谷仓中安装了 $N-1$ 条管道,用于在 $N$ 个牛棚之间运输牛奶($2 \leq N \leq 50,000$),牛棚方便地编号为 $1 \ldots N$。每条管道连接一对牛棚,所有牛棚通过这些管道相互连接。 FJ 正在 $K$ 对牛棚之间泵送牛奶($1 \leq K \leq 100,000$)。对于第 $i$ 对牛棚,你被告知两个牛棚 $s_i$ 和 $t_i$,这是牛奶以单位速率泵送的路径的端点。FJ 担心某些牛棚可能会因为过多的牛奶通过它们而不堪重负,因为一个牛棚可能会作为许多泵送路径的中转站。请帮助他确定通过任何一个牛棚的最大牛奶量。如果牛奶沿着从 $s_i$ 到 $t_i$ 的路径泵送,那么它将被计入端点牛棚 $s_i$ 和 $t_i$,以及它们之间路径上的所有牛棚。 ### 输入格式 输入的第一行包含 $N$ 和 $K$。 接下来的 $N-1$ 行每行包含两个整数 $x$ 和 $y$($x \ne y$),描述连接牛棚 $x$ 和 $y$ 的管道。 接下来的 $K$ 行每行包含两个整数 $s$ 和 $t$,描述牛奶泵送路径的端点牛棚。 ### 输出格式 输出一个整数,表示通过谷仓中任何一个牛棚的最大牛奶量。 ### 说明/提示 $2 \le N \le 5 \times 10^4,1 \le K \le 10^5$。

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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

说明

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