CF538E Demiurges Play Again

Shambambukli 和 Mazukta 两位神祇热衷于观察凡人的游戏。今天，他们发现了两位男子正在玩如下的游戏。 有一棵包含 $n$ 个节点的有根树，其中有 $m$ 个叶子节点（叶子节点指没有子节点的节点），树的边从父节点指向子节点。在树的叶子结点上，分别放置了整数 $1$ 到 $m$，每个数恰好出现在一个叶子上。 最初，树根节点上有一个棋子。两名玩家轮流操作，在每回合中，玩家可以将棋子从当前节点移动到其某个子节点；若无法进行移动，则游戏立即结束。游戏的结果为棋子最终停留的叶子节点上所放的数字。第一位玩家试图让游戏结果最大化，第二位玩家则试图尽量使结果最小。可以假设两位玩家都采取最优策略。 神祇有无上的权能，因此在游戏开始前，可以随意安排这些数字在叶子上的分布。Shambambukli 想要尽可能让游戏结果最大，而 Mazukta 则想让结果尽量小。如果两位分别布置数字并都采取最优策略，分别最终会达到什么结局？神祇都会选择最优的安排方式。

第一行包含一个整数 $n$，表示树的节点数（$1 \leq n \leq 2\cdot 10^5$）。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$），表示树中的一条边，该边从节点 $u_i$ 指向节点 $v_i$。保证所描述的图是一棵有根树，根为节点 $1$。

输出两个用空格分隔的整数，分别表示游戏结果可能的最大值和最小值。

考虑第一个样例。树有 3 个叶子节点：3、4 和 5。如果在节点 3 上放最大数字 3，那么第一位玩家会移动到此处，结果就是 3。另一方面，无论如何安排，第一位玩家都能保证结果至少为 2。 在第二个样例，无论怎样分配数字，第一位玩家都能沿着某条路径移动，最终到达叶子上的数字 3。 由 ChatGPT 5 翻译