T177911 『JROI-2』笨蛋的冰冻游戏

某日，笨蛋琪露诺看到了一群青蛙。 于是，她开始了冰冻青蛙的游戏。

给定一棵含 $n$ 个结点的树，树的每个结点上都有一只青蛙。 笨蛋琪露诺拥有冰冻青蛙程度的能力，所以她可以冰冻树上的青蛙。但是青蛙是很团结的生物（误），所以如果存在与被冰冻的青蛙所在结点直接连接的结点上有一只没有被冰冻的青蛙，那么在一次青蛙救援行动中，那只被冰冻的青蛙将被救起（变成没有被冰冻的状态）。注意到，在青蛙救援行动中，并不是每只不被冰冻的青蛙只能救起一只被冰冻的青蛙的。 琪露诺想要冰冻所有的青蛙，她可以使用冰冻法术，花费 $k$ 点灵力冰冻 $k$ 只青蛙，她每使用一次法术，就会休息一会，这时青蛙就会展开一次救援行动。 现在蓝对这个问题很感兴趣，她想知道，如果琪露诺想要在有限次法术内冰冻住所有青蛙，那么所有 $k$ 的最大值最小为多少。

**本题含多组数据**，第一行一个整数 $T$ 代表数据组数。 对于每组数据，第一行一个整数 $n$ 代表树的结点个数。 接下来 $n-1$ 行每行两个整数 $u,v$ 代表树的一条边。

对于每组数据一行一个整数代表所有 $k$ 的最大值最小为多少。

#### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（5 pts）：$\sum n \le 2$。 - Subtask 2（10 pts）：当前的树简化为了一条链。 - Subtask 3（10 pts）：当前的树简化为了一张菊花图。 - Subtask 4（10 pts）：当前的树为一棵二叉树。 - Subtask 5（20 pts ）：$\sum n \leq 5000$。 - Subtask 6（45 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \leq \sum n \leq 8 \times 10^6$。 Sub 1 ~ Sub 5 时限 1s，Sub 6 时限 3 秒。 考场给出的 Extra Example 是一个标准的四叉树，并无较高的强度，仅供参考调试。 ----- Source：[JROI-2 Summer Fun Round](https://www.luogu.com.cn/contest/30241) - T2 Idea&Sol&Std：[八云蓝](/user/149196) Data&Retest：[一只书虫仔](/user/114914)