Quartz 5

19721.最大异或结点

Properties1
tags字典树

4 min read

最大异或结点

小蓝有一棵树，树中包含 N 个节点编号为 0 ， 1 ， 2 ，……， N 一 1 ，其中每个结点上都有一个整数。他可以从树中任意选择两个不直接相连的结点 a 、 b 并获得分数，其中表示按位异或操作。
请问小蓝可以获得的最大分数是多少 ？
输入格式：
输入的第一行包含一个整数 N, 表示有 N 个结点。
第二行包含 N 个整数， ，…… ,, 相邻整数之间使用一个空格分隔。
第三行包含 N 个整数， ，…… ,, 相邻整数之间使用一个空格分隔，其中第i个整数表示i的父结点编号， 表示结点i没有父结点。
输出格式：
输出一行包含一个整数表示答案。

样例

Example

输入：
5
1 0 5 3 4
-1 0 1 0 1
输出：
7

思路

两个节点（数）的异或最大值，容易想到0-1字典树。但是题目要求两个节点不能相连，因此将每个节点相邻的节点记录下来，并在查询当前节点时先将相邻节点删掉，计算完后再添加回去。

答案

Java

import java.util.*;  
// 1:无需package  
// 2: 类名必须Main, 不可修改  
  
public class Main {  
  
    static final class Trie {  
        static final int BITS = 31;  
        static int[][] tree = new int[N * BITS][2];  
        static int[] cnt = new int[N * BITS];  
        static int total = 1;  
  
        void insert(int x) {  
            int u = 1;  
            for (int i = BITS; i >= 0; i--) {  
                int bit = (x >> i) & 1;  
                if (tree[u][bit] == 0) {  
                    tree[u][bit] = ++total;  
                }  
                u = tree[u][bit];  
                cnt[u]++;  
            }  
        }  
  
        void remove(int x) {  
            int u = 1;  
            for (int i = BITS; i >= 0; i--) {  
                int bit = (x >> i) & 1;  
                u = tree[u][bit];  
                cnt[u]--;  
            }  
        }  
  
        int queryMaxXor(int x) {  
            int u = 1, res = 0;  
            for (int i = BITS; i >= 0; i--) {  
                int bit = (x >> i) & 1;  
                if (tree[u][bit ^ 1] != 0 && cnt[tree[u][bit ^ 1]] > 0) {  
                    res |= (1 << i);  
                    u = tree[u][bit ^ 1];  
                } else {  
                    u = tree[u][bit];  
                }  
            }  
            return res;  
        }  
    }  
  
    static int N = (int) (1e5 + 10);  
    static int n;  
    static int[] x = new int[N];  
    static int f;  
    static List<Integer>[] neighbors = new List[N];  
    static Trie root = new Trie();  
    static int ans;  
  
  
    public static void main(String[] args) {  
        Scanner scan = new Scanner(System.in);  
        n = scan.nextInt();  
        for (int i = 0; i < n; i++) {  
            neighbors[i] = new ArrayList<>();  
        }  
        for (int i = 0; i < n; i++) {  
            x[i] = scan.nextInt();  
            root.insert(x[i]);  
        }  
        for (int i = 0; i < n; i++) {  
            f = scan.nextInt();  
            if (f != -1) {  
                neighbors[i].add(f);  
                neighbors[f].add(i);  
            }  
        }  
        scan.close();  
        for (int i = 0; i < n; i++) {  
            for (Integer j : neighbors[i]) {  
                root.remove(x[j]);  
            }  
            ans = Math.max(ans, root.queryMaxXor(x[i]));  
            for (Integer j : neighbors[i]) {  
                root.insert(x[j]);  
            }  
        }  
        System.out.println(ans);  
    }  
}

Backlinks