- 题目提供者 FarmerJohn2
- 评测方式 云端评测
- 标签 最近公共祖先,LCA 栈 树链剖分,树剖 USACO 2015 高性能
- 难度 提高+/省选-
- 时空限制 1000ms / 128MB
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