A6263 | $Max Flow P$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

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$，描述牛奶泵送路径的端点牛棚。

输出一个整数，表示通过谷仓中任何一个牛棚的最大牛奶量。

输入 #1

输出 #1

C++ 编辑器

输入

输出