SP16240 DCEPC11E - Easy Password

时间到了公元 2100 年。Pranjali 女士凭借她的智慧，使用一种能够冻结年龄的“神秘药水”存活至今。她将药水藏在一个高度机密的电子密码保护保险箱中。这套特殊系统由伟大的 Sameer 先生设计，不接受特定的字符串作为密码，而需要提交一棵“数字树”。对，你没听错，就是一棵树，作为密码。这棵树在结构和数值上必须完全匹配，才能解锁保险箱。但目前情况紧急，许多黑客正试图入侵系统。因此 Pranjali 女士感到不安，决定更换密码。不过，一些密码树过于脆弱，Sameer 先生建议不要使用。现在，你需要为 Pranjali 女士设计一个新的密码树，以确保她的“神秘药水”的安全。你将获得一个旧的密码树和 Sameer 先生提供的不合理密码树。Sameer 先生并不清楚旧密码树的确切结构，只知道当前黑客的攻击模式。 你需要创建的新密码树，其结构必须与旧密码树一致，但节点的顺序可以重新排列。新树中的任何节点都不能与不合理密码树中的节点在位置和数值上完全相同。节点的位置由从根节点到该节点的移动序列（左/右）决定。 如果有多个答案，请输出与旧密码树差异最小的那个。 两棵树的差异计算公式如下： \[ \text{Diff} = \left| \sum_{i=0}^{n-1} (\text{old}[ \text{node}[i] ] - \text{new}[ \text{node}[i] ]) \times 10^i \right| \] 这里 \( i \) 表示基于层序遍历的节点顺序。根节点对应 \( i = n-1 \)，依此类推。

第一行输入一个整数 \( t \)，表示测试用例的数量。每个测试用例第一行包含两个整数 \( n \) 和 \( m \)，分别表示旧密码树和不合理密码树的节点数量。接下来一行输入 \( n \) 个整数，表示旧密码树的节点值。接下来有 \( n \) 行，每行给出形式如 A B 的数对，第 \( i \) 行中的 A 和 B 分别表示以第 \( i \) 个节点（从0开始）的左子节点和右子节点指标。若无子节点，则用 -1 表示。 接下来一行输入 \( m \) 个整数，表示不合理密码树的节点值，随后以同样格式描述这颗树。

输出一个整数，表示新树和旧树的最小差异，若无法构造这样的树则输出 -1。

- \( 1 \le T \le 50 \) - \( 0 \le \text{node\_value} \le 9 \) - \( 1 \le n \le 18 \) 注意： 1. 新树可以与旧树相同。 2. 如果无法组合出合适的树，输出 -1。 3. 题中树均为二叉树。 ## 示例 ### 输入 ``` 1 3 3 5 4 8 1 2 -1 -1 -1 -1 5 1 8 1 2 -1 -1 -1 -1 ``` ### 输出 ``` 63 ``` ### 解释 根据题意，最优方案是以节点值为 4 为根节点，其左子节点为 8，右子节点为 5。此时，与旧密码树的最小差异为 63。 **本翻译由 AI 自动生成**