Max Flow

题目描述

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 担心有些牛栏可能会因为有太多牛奶经过而不堪重负，因为一个牛栏可能作为中转点出现在这 $K$ 条抽送路径中的许多条上。请帮助他确定任意牛栏被抽送通过的牛奶最大量。

如果牛奶沿从 $s_i$ 到 $t_i$ 的路径抽送，则它不仅计入端点牛栏 $s_i$ 和 $t_i$，也计入它们之间路径上的每一个牛栏。

输入格式

第一行输入包含 $N$ 和 $K$。 接下来的 $N-1$ 行每行包含两个整数 $x$ 和 $y$（$x \ne y$），描述连接牛栏 $x$ 与牛栏 $y$ 的一根管道。 接下来的 $K$ 行每行包含两个整数 $s$ 和 $t$，描述一条正在抽送牛奶的路径的端点牛栏。

输出格式

输出一个整数，表示牛棚中任意牛栏被抽送通过的牛奶最大量。

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

9

提示

题目来源：Brian Dean

标签: USACO|2015|Platinum

来源

USACO|2015|Platinum