CF581F Zublicanes and Mumocrates

到了伯兰德的选举季。最受欢迎的政党当然是 zublicanes 和 mumocrates。这两个政党的竞选活动包括在伯兰德首都的 $n$ 个主广场举行众多示威游行。每个广场只能举办一个政党的示威活动，否则可能会导致骚乱。另一方面，两党都申请了举办大量示威的名额，因此所有广场都必须有示威活动。现在，首都管理部门将把所有广场分配给两大政党。 有一些广场之间通过 $n-1$ 条双向道路相连，使得任意两广场之间都只有一条唯一的路径可以到达。某些广场处于首都的边缘，这意味着它们只通过一条道路与另一个广场相连，这样的广场称为“死胡同广场”。 市长要求分配广场时，必须保证两党分得的“死胡同广场”数量相等。保证城市中“死胡同广场”的数目是偶数。 为了防止 zublicanes 与 mumocrates 之间发生冲突，决定要最小化属于不同政党的广场之间的道路数目。你作为广场分配部门的开发者，应当计算出这个最小可能的道路数。

输入的第一行包含一个整数 $n$（$2 \leq n \leq 5000$），表示伯兰德首都的主广场数。 接下来的 $n-1$ 行中，每行包含两个整数 $x,y$（$1 \leq x, y \leq n, x \neq y$），表示一条连接编号为 $x$ 和 $y$ 的广场的道路。所有广场用 $1$ 到 $n$ 的整数编号。保证城市中“死胡同广场”的数目是偶数。

输出一个整数，表示在满足条件的广场分配方案下，不同政党的广场之间的最少道路数。

由 ChatGPT 5 翻译