请升级 HydroOJ 到 4.19.0 以上版本以正常使用此插件功能。

J. 从叶子走到根(hard)

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一棵以节点1为根节点的树，树的每个叶子节点上都有一个虫子，每个虫子都会先后朝着根节点爬行，每当一个虫子到一个无所有者的节点，就会将这个节点收入麾下，并获得1块钱。

当一个虫子爬到了根节点，或者爬到有所有者的节点，就停止爬行。

前一个虫子爬完了，后一个虫子才能开始爬。

你可以决定虫子的爬行顺序，请尽可能让最穷的虫子拥有的钱最多。

第一行输入一个正整数 $t$ ，表示一共有 $t$ 个测试样例 $(1 \le t \le 10^5)$

对于每个测试样例

对于每个测试样例，输出一个正整数，表示最穷的虫子可能拥有的最多的钱是多少。

1
3
1