首页 > 试题广场 >

Tree VI

[编程题]Tree VI

系统中有一棵n个点的完全k叉树，现给出它的DFS先序遍历序列 $a_i$ ，请你还原这棵树，并返回加密后的答案。

答案加密方法：所有边两个端点异或的和，即 $\sum\limits_{i=1}^{n-1}u_i\ xor\ v_i$ ，其中 $(u_i, v_i)$ 为一条树上的边。

下面给出完全二叉树的定义：若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层所有的结点都连续集中在最左边。

请你根据这个定义进行适度推广，得到完全k叉树的含义。

示例1

输入

2,[1,2,3,4,5]

树边为(1, 2), (1, 5), (2, 3), (2, 4)，加密过程为(1^2)+(1^5)+(2^3)+(2^4)，答案为14。

样例1构成的完全二叉树为：

示例2

3,[1,2,3,4,5]

树边为(1, 2), (1, 4), (1, 5), (2, 3)，加密过程为(1^2)+(1^4)+(1^5)+(2^3)，答案为13。

样例2构成的完全三叉树为：

数据满足：

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

树 dfs

难度：

0条回答 1收藏 612浏览

查看代码

扫一扫，把题目装进口袋