Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届省赛真题-最大异或结点
题目 3233:

蓝桥杯2024年第十五届省赛真题-最大异或结点

时间限制: 3s 内存限制: 512MB 提交: 248 解决: 14

题目描述

小蓝有一棵树,树中包含 N 个结点,编号为 0, 1, 2, · · · , N − 1 ,其中每个结点上都有一个整数 Xi 。他可以从树中任意选择两个不直接相连的结点 a 、b并获得分数 Xa ⊕ Xb ,其中 ⊕ 表示按位异或操作。

请问小蓝可以获得的最大分数是多少?

输入格式

输入的第一行包含一个整数 N ,表示有 N 个结点。

第二行包含 N 个整数 X1, X2, · · · , XN ,相邻整数之间使用一个空格分隔。

第三行包含 N 个整数 F1, F2, · · · , FN ,相邻整数之间使用一个空格分隔,其中第 i 个整数表示 i 的父结点编号,Fi = −1 表示结点 i 没有父结点。

输出格式

输出一行包含一个整数表示答案。

样例输入

5
1 0 5 3 4
-1 0 1 0 1

样例输出

7

提示

【样例说明】
选择编号为 3 和 4 的结点,x3 = 3 ,x4 = 4 ,他们的值异或后的结果为3 ⊕ 4 = 7 。
【评测用例规模与约定】

对于 50% 的评测用例,1 ≤ N ≤ 1000 ;

对于所有评测用例,1 ≤ N ≤ 105, 0 ≤ Xi ≤ 231 − 1 ,−1 ≤ Fi ≤ N ,Fi , 0 。

标签