Leetcode 2791. Count Paths That Can Form a Palindrome in a Tree

[Woodyiiiiiii]

2791. Count Paths That Can Form a Palindrome in a Tree

2791. Count Paths That Can Form a Palindrome in a Tree

类似题目：
1371. Find the Longest Substring Containing Vowels in Even Counts
1542. Find Longest Awesome Substring

讲解：
用位运算处理

---

路径字符串rearrange过后可以形成回文字符串，说明要么所有字符出现偶数次，要么只有一个字符出现奇数次，其他都出现偶数次；所以我们可以用异或运算状态压缩来判断是否回文。

如果把这道题改成数组，类似No.1371，我们就知道用状压+前缀和哈希来解决。同理，放到树结构也可以这么想。因为树的特殊性，两个节点组成的路径会经过根节点0，所以同样可以用哈希来存储 状态-个数 的关系。

class Solution {
    Map<Integer, Set<int[]>> g;
    Map<Integer, Long> memo;
    long ans = 0;

    public long countPalindromePaths(List<Integer> parent, String s) {
        // build map
        g = new HashMap<>();
        for (int i = 1; i < parent.size(); i++) {
            g.putIfAbsent(parent.get(i), new HashSet<>());
            g.get(parent.get(i)).add(new int[]{i, 1 << (s.charAt(i) - 'a')});
        }
        // cache
        memo = new HashMap<>();
        memo.put(0, 1L);

        dfs(0, 0);
        return ans;
    }

    private void dfs(int cur, int mask) {
        for (int[] arr : g.getOrDefault(cur, Collections.emptySet())) {
            int next = arr[0];
            int w = arr[1];
            int nextMask = mask ^ w;
            ans += memo.getOrDefault(nextMask, 0L);
            for (int i = 0; i < 26; i++) {
                ans += memo.getOrDefault(nextMask ^ (1 << i), 0L);
            }
            memo.put(nextMask, memo.getOrDefault(nextMask, 0L) + 1);
            dfs(next, nextMask);
        }
    }
}