
 2K通过
 3.9K提交
 题目提供者 FarmerJohn2
 评测方式 云端评测
 标签 最近公共祖先,LCA 栈 树链剖分,树剖 USACO 2015 高性能
 难度 提高+/省选
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
Farmer John has installed a new system of $N1$ 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 eachother 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(2≤N≤50,000)个隔间之间安装了N1根管道，隔间编号从1到N。所有隔间都被管道连通了。
FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。
输入输出格式
输入格式：The first line of the input contains $N$ and $K$.
The next $N1$ 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.