题目

最大异或结点

解题思路(01字典树 + 动态维护)

本题要求在一棵树中选出两个不直接相连的节点，使得它们的点权异或值最大。暴力枚举所有非相邻点对的时间复杂度为 ​O(N^2)，无法通过 ​N=10^5 的数据规模。我们采用 01 字典树（Binary Trie） 配合 动态删除与恢复 的技巧，在 ​O(N \log V) 时间内高效求解。

什么是 01 字典树？

01 字典树是普通字典树（Trie）在整数二进制表示上的应用。它将每个整数视为一个由 0 和 1 组成的字符串（通常固定为 32 位），从高位到低位插入 Trie 中。

• 每个节点最多有两个子节点：children[0] 和 children[1]
• 插入、删除、查询操作的时间复杂度均为 ​O(32) = O(1)

它的核心用途是：给定一个数 ​x，在集合中快速找到一个数 ​y，使得 ​x \oplus y 最大。

原理：异或结果要大，就要让高位尽可能为 1。因此从最高位开始，贪心地选择与 ​x 当前位相反的 bit 路径（即若 ​x 当前位是 0，就优先走 1；反之亦然）。

整体策略：枚举 + 动态维护合法集合

由于不能选择相邻节点，我们采用以下策略：

1. 预处理：将所有节点的值插入 01 字典树。
2. 枚举每个节点 ​a：
   • 临时从字典树中删除所有与 ​a 相邻的节点的值（确保后续查询不会选到邻居）
   • 查询当前字典树中与 ​X[a] 异或最大的值
   • 更新全局答案
   • 恢复（重新插入）刚才删除的邻居值
3. 输出最大异或值

为什么可行？
树有 ​N-1 条边，每条边在枚举两个端点时各被处理一次，总删除/插入次数为 ​2(N-1)，加上 ​N 次查询，总操作数为 ​O(N)，每次操作 ​O(32)，整体高效。

如何安全删除？

为支持重复值和多次删除，我们在 Trie 节点中维护一个 count 计数器：

• 插入时，路径上每个节点 count++
• 删除时，路径上每个节点 count--，若减到 0 则断开指针
• 查询时只走 count > 0 的路径

这样即使多个相同值存在，也能正确维护。

参考代码

import java.util.*;

public class Main {
    // Trie 节点定义
    static class TrieNode {
        TrieNode[] children = new TrieNode[2];
        int count = 0; // 记录经过该节点的数字个数，用于安全删除
    }

    // 01 字典树封装
    static class BinaryTrie {
        private final TrieNode root;
        private final int BITS = 31; // 处理 0~2^31-1 范围的非负整数

        public BinaryTrie() {
            root = new TrieNode();
        }

        // 插入一个整数到字典树（从高位到低位）
        public void insert(int x) {
            TrieNode node = root;
            for (int i = BITS; i >= 0; i--) {
                int bit = (x >>> i) & 1; // 无符号右移取第 i 位
                if (node.children[bit] == null) {
                    node.children[bit] = new TrieNode();
                }
                node = node.children[bit];
                node.count++; // 路径上每个节点计数+1
            }
        }

        // 从字典树中删除一个整数（必须已存在）
        public void delete(int x) {
            TrieNode node = root;
            for (int i = BITS; i >= 0; i--) {
                int bit = (x >>> i) & 1;
                TrieNode next = node.children[bit];
                // 理论上不会为null，因为要删的数一定存在
                // 减少计数，若为0则断开链接
                next.count--;
                if (next.count == 0) {
                    node.children[bit] = null; // 断开引用
                    return;
                }
                node = next;
            }
        }

        // 查询与 x 异或能得到的最大值
        public int queryMaxXor(int x) {
            TrieNode node = root;
            // 若字典树为空，返回0
            if (node.children[0] == null && node.children[1] == null) {
                return 0;
            }
            int res = 0;
            for (int i = BITS; i >= 0; i--) {
                int bit = (x >>> i) & 1;
                int desired = 1 - bit; // 希望走相反的bit以使异或结果为1

                // 优先尝试走 desired 路径
                if (node.children[desired] != null && node.children[desired].count > 0) {
                    res |= (1 << i); // 第i位可置1
                    node = node.children[desired];
                } 
                // 否则只能走相同bit路径（异或结果为0，res该位保持0）
                else if (node.children[bit] != null && node.children[bit].count > 0) {
                    node = node.children[bit];
                } else {
                    break; // 无路可走（理论上不会发生）
                }
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] X = new int[n];
        for (int i = 0; i < n; i++) {
            X[i] = sc.nextInt();
        }
        int[] F = new int[n];
        for (int i = 0; i < n; i++) {
            F[i] = sc.nextInt();
        }

        // 构建无向树的邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            int parent = F[i];
            adj.get(i).add(parent);
            adj.get(parent).add(i);
        }

        // 初始化字典树，并插入所有节点值
        BinaryTrie trie = new BinaryTrie();
        for (int value : X) {
            trie.insert(value);
        }

        int ans = 0;
        // 枚举每个节点 a
        for (int a = 0; a < n; a++) {
            // 临时删除 a 的所有邻居（确保不选相邻节点）
            for (int neighbor : adj.get(a)) {
                trie.delete(X[neighbor]);
            }

            // 查询与 X[a] 异或的最大值（此时字典树不含邻居）
            int maxXor = trie.queryMaxXor(X[a]);
            ans = Math.max(ans, maxXor);

            // 恢复邻居值（为下一次枚举做准备）
            for (int neighbor : adj.get(a)) {
                trie.insert(X[neighbor]);
            }
        }

        System.out.println(ans);
    }
}

最长回文子串

解题思路(中心扩展法与字符串哈希+二分法)

给定一个字符串，求其最长回文子串的长度。

回文的结构特性

回文子串可分为两类：

• 奇数长度：存在一个中心字符，如 "aba"；
• 偶数长度：中心位于两个字符之间，如 "abba"。

利用这一特性，我们可以从“中心”出发，向两侧扩展验证回文。

方法一：中心扩展法（简单直观）

该方法枚举每个可能的回文中心，并尝试向两边扩展：

• 对每个位置 i，分别考虑以 i 为中心（奇数长度）和以 i 与 i+1 之间为中心（偶数长度）；
• 每次扩展时，只要左右字符相等就继续，否则停止；
• 记录所有扩展中得到的最大长度。

时间复杂度为 ​O(n^2)，空间复杂度 ​O(1)，代码简洁，适用于中小规模数据。

方法二：字符串哈希 + 二分（高效通用）

当字符串较长（如 ​n = 10^5）时，可使用字符串哈希将子串比较优化至 ​O(1)，再结合二分搜索加速查找过程。

具体做法：

• 预处理正向哈希和反向哈希数组（使用双模数降低冲突概率）；
• 枚举每个可能的回文中心；
• 对每个中心，二分其最大扩展半径：
  • 对于奇数长度，中心为 i，检查区间 [i−r, i+r]；
  • 对于偶数长度，中心在 i 和 i+1 之间，检查区间 [i−r+1, i+r]；
• 利用哈希值快速判断子串是否等于其反转，从而验证回文。

该方法总时间复杂度为 ​O(n \log n)，适合大规模数据，是“字符串哈希与二分”技巧的典型应用。

参考代码

方法一：中心扩展法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(longestPalindrome(s));
    }

    private static int longestPalindrome(String s) {
        if (s.isEmpty()) return 0;
        int maxLen = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            // 奇数长度：以 i 为中心
            int len1 = expand(s, i, i);
            // 偶数长度：以 i 和 i+1 为中心
            int len2 = expand(s, i, i + 1);
            maxLen = Math.max(maxLen, Math.max(len1, len2));
        }
        return maxLen;
    }

    // 从 left 和 right 开始向外扩展，返回回文长度
    private static int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

方法二：字符串哈希 + 二分

import java.util.*;

public class Main {
    private static final long MOD1 = 1_000_000_007L;
    private static final long MOD2 = 1_000_000_009L;
    private static final long BASE = 131L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        System.out.println(longestPalindrome(s));
    }

    private static int longestPalindrome(String s) {
        int n = s.length();
        if (n == 0) return 0;
        char[] chars = s.toCharArray();

        // 正向哈希（双模数）
        long[] forwardHash1 = new long[n + 1];
        long[] forwardHash2 = new long[n + 1];
        // 反向哈希：将原字符串反转后计算的前缀哈希
        long[] reverseHash1 = new long[n + 1];
        long[] reverseHash2 = new long[n + 1];
        // 预处理 base 的幂次
        long[] power1 = new long[n + 1];
        long[] power2 = new long[n + 1];
        power1[0] = 1;
        power2[0] = 1;

        // 构建正向哈希
        for (int i = 0; i < n; i++) {
            forwardHash1[i + 1] = (forwardHash1[i] * BASE + chars[i]) % MOD1;
            forwardHash2[i + 1] = (forwardHash2[i] * BASE + chars[i]) % MOD2;
            power1[i + 1] = (power1[i] * BASE) % MOD1;
            power2[i + 1] = (power2[i] * BASE) % MOD2;
        }

        // 构建反向哈希（等价于对 reversed(s) 做前缀哈希）
        for (int i = 0; i < n; i++) {
            reverseHash1[i + 1] = (reverseHash1[i] * BASE + chars[n - 1 - i]) % MOD1;
            reverseHash2[i + 1] = (reverseHash2[i] * BASE + chars[n - 1 - i]) % MOD2;
        }

        int maxLen = 1;

        // 枚举奇数长度回文的中心
        for (int center = 0; center < n; center++) {
            // 最大可能的扩展半径（不能越界）
            int maxRadius = Math.min(center, n - 1 - center);
            int leftRadius = 0;
            int rightRadius = maxRadius;

            // 二分查找最大可行半径
            while (leftRadius < rightRadius) {
                int midRadius = (leftRadius + rightRadius + 1) / 2;
                int leftIndex = center - midRadius;
                int rightIndex = center + midRadius;
                if (isPalindrome(forwardHash1, forwardHash2, reverseHash1, reverseHash2,
                        power1, power2, n, leftIndex, rightIndex)) {
                    leftRadius = midRadius; // 当前半径可行，尝试更大
                } else {
                    rightRadius = midRadius - 1; // 不可行，缩小半径
                }
            }
            maxLen = Math.max(maxLen, 2 * leftRadius + 1);
        }

        // 枚举偶数长度回文的中心（位于 center 和 center+1 之间）
        for (int center = 0; center < n - 1; center++) {
            // 基础条件：相邻字符必须相等
            if (chars[center] != chars[center + 1]) continue;

            // 初始半径为 1（已知 [center, center+1] 是回文）
            int maxRadius = Math.min(center + 1, n - 1 - center);
            int leftRadius = 1;
            int rightRadius = maxRadius;

            while (leftRadius < rightRadius) {
                int midRadius = (leftRadius + rightRadius + 1) / 2;
                // 偶数回文区间：[center - midRadius + 1, center + midRadius]
                int leftIndex = center - midRadius + 1;
                int rightIndex = center + midRadius;
                if (isPalindrome(forwardHash1, forwardHash2, reverseHash1, reverseHash2,
                        power1, power2, n, leftIndex, rightIndex)) {
                    leftRadius = midRadius;
                } else {
                    rightRadius = midRadius - 1;
                }
            }
            maxLen = Math.max(maxLen, 2 * leftRadius);
        }

        return maxLen;
    }

    /**
     * 判断子串 s[left..right] 是否为回文（使用双模数哈希）
     */
    private static boolean isPalindrome(
            long[] forwardHash1, long[] forwardHash2,
            long[] reverseHash1, long[] reverseHash2,
            long[] power1, long[] power2,
            int n, int left, int right) {

        if (left < 0 || right >= n) {
            return false;
        }

        int length = right - left + 1;

        // 计算正向子串的哈希值
        long hashForward1 = (forwardHash1[right + 1] -
                (forwardHash1[left] * power1[length]) % MOD1 + MOD1) % MOD1;
        long hashForward2 = (forwardHash2[right + 1] -
                (forwardHash2[left] * power2[length]) % MOD2 + MOD2) % MOD2;

        // 原串 [left, right] 在反转串中的对应区间是 [n-1-right, n-1-left]
        int revLeft = n - 1 - right;
        int revRight = n - 1 - left;

        // 计算反转子串的哈希值
        long hashReverse1 = (reverseHash1[revRight + 1] -
                (reverseHash1[revLeft] * power1[length]) % MOD1 + MOD1) % MOD1;
        long hashReverse2 = (reverseHash2[revRight + 1] -
                (reverseHash2[revLeft] * power2[length]) % MOD2 + MOD2) % MOD2;

        // 双模数哈希均相等，认为是回文
        return hashForward1 == hashReverse1 && hashForward2 == hashReverse2;
    }
}