Description：

给一颗 $n$ 个节点的树，每个边上有一个守卫。有 $m$ 个居民，每个居民有一个散步路径。一个居民高兴当且仅当他获得了一个宠物或者他散步的路径上所有的守卫都有宠物。求最少需要几个宠物能让所有居民高兴。输出方案。

$1\leqslant n\leqslant 20000$

Solution：

考虑最小割每个人建一个点，每条边建一个点，把代表每个人的点和 $S$ 连容量为 $1$ 的边，每个人和他经过的所有路径连 $\infty$ 边，所有边和汇点连一的边，然后跑最小割就是答案，但是这样连的边数就太多了，因此我们可以用倍增优化连边，最后输出方案就是看人和源点是否相连，边和汇点是否相连。

Code：

代码当然是咕掉了