题目大意
A 国一共有 $n$ 个城市且有 $n-1$ 条双向道路，且任意两个城市都可以通过道路互相到达。
现在 B 国给出了两个城市的集合 $X,Y$，你需要摧毁若干条 A 国的道路，使得任意一个在 X 中的城市无法到达任何一个 Y 中的城市。
现在给定每条道路摧毁需要付出的代价，求一个代价之和最小的方案。
数据范围
$ nle 2 imes 10^5 $
$ 1 le w le 10^9 $ （$w$ 表示摧毁道路的代价）
分析
最小割
这道题实际上是求无向图最小割，因此可以套网络流的模板。
建图：
- 将 $X$ 中的点缩成一点 $s$，将 $Y$ 中的点缩成一点 $t$
这里我有一个疑问：缩点之后得到的无向图中的每条边 $(u,v)$，在流网络中要加两条有向边 $(u o v) $ 和 $(v o u)$ 吗？
还是说可以先进行一次 DFS 或 BFS 将边从 $s$ 到 $t$ 定向？
树形 DP
这里介绍一个树形 DP 的解法。
为了便于表述，给树的节点标号。 $X$ 中的节点标号为 1，$Y$ 中的节点标号为 $2$，余下的节点标号为 $0$ 。
我们称一棵有根树拆了若干条边（也可能一条边都不拆）之后是合法的， 当且仅当拆边之后的图中不存在两个标号分别为 1 和 2 的连通节点。
我们将所有合法的图分成三类：
- 存在一个标号为 1 的点与根节点连通
- 存在一个标号为 2 的点与根节点连通
- 不属于前两类
据此不难定义 DP状态，写出转移方程。
至此，我们将这个问题转化成了一个典型的（子树合并）树形 DP 问题。