CF238C World Eater Brothers

你一定听说过那一对梦想统治世界的兄弟。在之前的所有计划都失败后，这次他们决定合作以统治世界。 如你所知，世界上有 $n$ 个国家。这些国家通过 $n-1$ 条有向道路连接。如果不考虑道路的方向，每一对国家之间都存在一条唯一的路径，并且每条道路最多经过一次。 兄弟俩中的每个人都想在某个国家建立自己的统治，然后可以通过有向道路，从他的国家出发控制所有能到达的国家。 如果存在至多两个国家供兄弟俩选择（并在这些国家建立统治），使得世界上任意其他国家都能被他们中至少一人控制，则两兄弟就能统治世界。为了实现这一目标，他们希望最少地改变道路的方向。你的任务是计算最少需要改变方向的道路数。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 3000$）。接下来的 $n-1$ 行，每行有两个用空格分隔的整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n；a_i \neq b_i$），表示存在一条从国家 $a_i$ 到国家 $b_i$ 的道路。 假定国家编号为 $1$ 到 $n$。保证对于每对国家，如果不考虑道路方向，均存在一条唯一的路径连接它们，并且每条道路最多经过一次。

输出仅一行，表示为使兄弟俩能够统治世界，最少需要改变方向的道路数。

由 ChatGPT 5 翻译