#P13092. [FJCPC 2025] 二叉树

    ID: 12805 Type: RemoteJudge 1000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>2025福建Special JudgeXCPC

[FJCPC 2025] 二叉树

题目描述

墨菲特非常喜欢完美的树。在某一天,他决定用茂凯给的神秘种子自己种一棵树。

这颗种子拥有非常旺盛的生命力。将这颗种子种下后,如果我们把第一天种下的种子记为初始的叶子节点,那么从第二天开始,每个前一天长出来的叶子节点,都会长出两个新的叶子节点。换句话说,如果这颗树生长了 kk 天,那么它就是一棵拥有 2k12^k - 1 个节点的满二叉树。

由于其迅速的生长速度,墨菲特很快就能得到一棵拥有很多节点的满二叉树,他认为满二叉树是十分完美的。

茂凯也知道墨菲特非常喜欢树,因此他带来了一份礼物:由同样的神秘种子种出来的一棵树(大小不一定相同)。然而墨菲特已经有一颗这样的树了,两棵树的存放不太方便,于是他在两棵树之间连接了一条新的边,这样就是一棵树了。

显然,这样的树已经不是完美的二叉树了,因此墨菲特很快就把他丢在了角落。

过了很久很久之后,墨菲特又想起来了这棵由两棵满二叉树连接形成的新树,他想要重新把这棵树拆成两棵满二叉树,但是他已经忘记哪条边是他额外添加上去的了。

希望聪明的你可以帮助墨菲特解决这个问题。

形式化地,给定一棵树,你需要删除其中的一条边,使得分成的两棵树都是满二叉树,保证至少存在一个解。

*所有叶结点的深度均相同,且所有非叶节点的子节点数量均为 22 的二叉树称为满二叉树。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 TT ( 1T1051 \le T \le 10^5 ) ,表示测试数据的数量。接下来是测试数据的描述。

每组测试数据的第一行包含一个正整数 n (2n2172)n\ (2 \le n \le 2^{17} - 2) ,表示墨菲特手上的树的节点个数。

接下来 n1n - 1 行,每行两个由空格分开的正整数 ui,vi (1ui,vin)u_i, v_i\ (1 \le u_i, v_i \le n) ,表示树上的一条边 (ui,vi)(u_i, v_i) 。输入保证给定的边集构成一棵树。

另外,保证 n106\sum n \le 10^6

输出格式

对于每一组测试数据,输出一行一个正整数 ii ,表示如果删除了给定边集中的第 ii 条边 (ui,vi)(u_i, v_i) ,分成的两棵树都是满二叉树。保证这样的解一定存在。如果有多个可行的解,输出任意一个即可。

3
2
1 2
14
8 14
5 10
9 14
2 4
12 13
7 14
1 5
2 6
2 1
7 12
3 5
12 4
11 2
10
1 2
1 3
2 4
2 5
3 6
3 7
1 8
8 9
8 10
1
4
7

提示

第二组样例的树如上图所示,可以发现,只有删除边 (2,4)(2, 4) 是合法的。

第三组样例的树如下图所示,可以发现,删除边 (1,2),(1,3),(1,8)(1, 2), (1, 3), (1, 8) 都是合法的,你可以输出任意一种。