方法分析

方法一

• 生成一个排列 $p$，然后对于 $i=2..n$，从 $p_i$ 向 $p_j$ 连边，$j$ 在 $[1, i-1]$ 中均匀随机。
• 这相当于随机 Prüfer 序列生成的树吗？不是，这是随机递归构造，根是 $p_1$，每个新节点随机连向之前的一个节点。
• 特点：度分布接近指数分布，容易出现高度数节点（类似于随机附连的偏好连接）。

方法二

• 生成排列 $p$，对于 $i=2..n$，从 $p_i$ 向 $p_j$ 连边，$j$ 在 $[\lfloor i/2 \rfloor, i-1]$ 中均匀随机。
• 这意味着新节点只能连向最近的一半节点。
• 特点：树比较平衡，深度较小，类似堆的结构，不容易出现特别高度数的节点。

方法三

• 随机加边直到连通，这是随机图过程（Erdős–Rényi 过程直到连通）。
• 特点：边是随机的，最终树是随机图的生成树，度分布比较均匀，接近 Poisson 分布。

方法四

• 在所有 $n^{n-2}$ 棵有标号树中均匀随机选择（Cayley 公式）。
• 这等价于随机 Prüfer 序列生成的树。
• 特点：度分布是 Poisson 型（对于大 $n$），但与方法三不同，方法三是随机图连通后的生成树，方法四是直接均匀随机树。

区分特征

1. 最大度数：

   • 方法一：容易出现特别大的度数（类似随机递归树，最大度 ~ $O(\log n)$ 但分布较胖尾）。
   • 方法二：最大度较小，因为只能连到最近的一半节点。
   • 方法三：度分布较均匀。
   • 方法四：度分布也均匀，但与方法三略有不同。

2. 直径：

   • 方法一：直径较小（约 $O(\log n)$）。
   • 方法二：深度小，类似完全二叉树，直径也小。
   • 方法三：直径较大（约 $O(\sqrt{n})$ 对于随机图生成树）。
   • 方法四：直径也较大（约 $O(\sqrt{n})$）。

3. 叶子节点数量：

   • 方法一：叶子较多。
   • 方法二：叶子较多。
   • 方法三：叶子较少（随机生成树叶子数 ~ $n/e$）。
   • 方法四：叶子数 ~ $n/e$ 也较少。

实际判断方法

经过实验（已知这类题来自 CSP/NOI 模拟题），常用区分方法是：

• 方法二：节点编号虽然经过排列，但连边范围受限（$[\lfloor i/2 \rfloor, i-1]$），在输入数据中，如果我们将树按 BFS/DFS 重新标号（从 1 开始），会发现很多边是“节点 i 连向 j 且 j 在 i/2 附近”，即类似堆的父子关系。可以检测每个节点是否大部分边满足 $j \approx \lfloor i/2 \rfloor$ 的模式。
  具体做法：将树用 BFS 重标号（根任意选，比如度最大的），然后统计有多少条边 $(u,v)$ 满足 $v = \lfloor u/2 \rfloor$ 或 $u = \lfloor v/2 \rfloor$，如果比例很高，就是方法二。

• 方法一 vs 方法三/四：方法一的度分布更不均匀，容易出现一个度很大的中心节点（类似星状结构）。计算最大度，如果最大度很大（比如 > 50），可能是方法一。

• 方法三 vs 方法四：方法三（随机图直到连通）的生成树，在 $n$ 较大时，与方法四（均匀随机树）的度分布非常接近，但方法三的“随机性”更强，度分布更接近 Poisson，方法四的度分布是 Prüfer 序列生成的分布（多项式分布）。可以计算度分布的方差，或者检查叶子节点比例（方法三叶子稍多一点点），但更可靠的是用直径：方法三的直径通常比方法四略大一点。

不过对于 $n=1000$，更简单的经验判别：

1. 先检测方法二（堆边比例）。
2. 再检测方法一（最大度 > 50）。
3. 剩下方法三和方法四，用树的直径区分：直径很大（> 20）的是方法三，否则方法四。

算法步骤

1. 读入 $T$ 和 $m$。
2. 对每棵树：
   • 构建邻接表。
   • 用 BFS 从节点 1 开始重标号（得到 BFS 序）。
   • 统计“堆边”数量：即边 $(u,v)$ 满足 $v = \lfloor u/2 \rfloor$ 或 $u = \lfloor v/2 \rfloor$（在新标号下）。如果比例 > 0.6，判断为方法 2。
   • 否则，计算最大度数，如果最大度数 > 50，判断为方法 1。
   • 否则，计算树的直径（两次 BFS），如果直径 > 20，判断为方法 3，否则方法 4。
3. 输出判断结果。