#P13092. [FJCPC 2025] 二叉树
[FJCPC 2025] 二叉树
题目描述
墨菲特非常喜欢完美的树。在某一天,他决定用茂凯给的神秘种子自己种一棵树。
这颗种子拥有非常旺盛的生命力。将这颗种子种下后,如果我们把第一天种下的种子记为初始的叶子节点,那么从第二天开始,每个前一天长出来的叶子节点,都会长出两个新的叶子节点。换句话说,如果这颗树生长了 天,那么它就是一棵拥有 个节点的满二叉树。
由于其迅速的生长速度,墨菲特很快就能得到一棵拥有很多节点的满二叉树,他认为满二叉树是十分完美的。
茂凯也知道墨菲特非常喜欢树,因此他带来了一份礼物:由同样的神秘种子种出来的一棵树(大小不一定相同)。然而墨菲特已经有一颗这样的树了,两棵树的存放不太方便,于是他在两棵树之间连接了一条新的边,这样就是一棵树了。
显然,这样的树已经不是完美的二叉树了,因此墨菲特很快就把他丢在了角落。
过了很久很久之后,墨菲特又想起来了这棵由两棵满二叉树连接形成的新树,他想要重新把这棵树拆成两棵满二叉树,但是他已经忘记哪条边是他额外添加上去的了。
希望聪明的你可以帮助墨菲特解决这个问题。
形式化地,给定一棵树,你需要删除其中的一条边,使得分成的两棵树都是满二叉树,保证至少存在一个解。
*所有叶结点的深度均相同,且所有非叶节点的子节点数量均为 的二叉树称为满二叉树。
输入格式
输入包含多组测试数据。
第一行包含一个正整数 ( ) ,表示测试数据的数量。接下来是测试数据的描述。
每组测试数据的第一行包含一个正整数 ,表示墨菲特手上的树的节点个数。
接下来 行,每行两个由空格分开的正整数 ,表示树上的一条边 。输入保证给定的边集构成一棵树。
另外,保证 。
输出格式
对于每一组测试数据,输出一行一个正整数 ,表示如果删除了给定边集中的第 条边 ,分成的两棵树都是满二叉树。保证这样的解一定存在。如果有多个可行的解,输出任意一个即可。
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
提示
第二组样例的树如上图所示,可以发现,只有删除边 是合法的。
第三组样例的树如下图所示,可以发现,删除边 都是合法的,你可以输出任意一种。