树中可以形成回文的路径数

难度: Hard

给你一棵树（即，一个连通、无向且无环的图），根节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以 重新排列 形成回文的所有节点对 (u, v) ，并返回节点对的数目。

如果一个字符串正着读和反着读都相同，那么这个字符串就是一个回文。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "acaabc"
输出：8
解释：符合题目要求的节点对分别是：
- (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。
- (2,3)，路径上字符形成的字符串是 "aca" ，满足回文定义。
- (1,5)，路径上字符形成的字符串是 "cac" ，满足回文定义。
- (3,5)，路径上字符形成的字符串是 "acac" ，可以重排形成回文 "acca" 。

示例 2：

输入：parent = [-1,0,0,0,0], s = "aaaaa"
输出：10
解释：任何满足 u < v 的节点对 (u,v) 都符合题目要求。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对于所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文字母组成

Submission

运行时间: 372 ms

内存: 45.2 MB

from collections import defaultdict


class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        count = defaultdict(int)
        N = len(parent)
        bitset = [None] * N
        ans = 0
        def get_bitset(i):
            if bitset[i] is not None:
                return bitset[i]
            p = parent[i]
            if p == -1:
                b = 0
            else:
                ci = ord(s[i]) - ord('a')
                b = get_bitset(p) ^ (1 << ci)
            bitset[i] = b
            count[b] += 1
            return b

        for i in range(len(parent)):
            get_bitset(i)
        for k, v in count.items():
            ans += v * (v - 1) // 2
            x = k
            while x:
                lowbit = (x & (-x))
                ans += v * count.get(k ^ lowbit, 0)
                x -= lowbit
        return ans

Explain

此题解采用了位运算与哈希表来高效处理问题。首先，通过DFS遍历树的每个节点，利用位运算来记录从根节点到当前节点的路径上字符出现的奇偶性。具体地，为每个字符分配一个位（例如字符'a'对应第0位），若该字符在路径上出现奇数次则对应位为1，偶数次则为0。这样，每个节点的路径可以通过一个整数（位集合）来唯一表示。使用哈希表来统计每种位集合的出现次数。在统计完所有节点后，再次遍历哈希表来计算可能的回文路径数。如果两个节点的路径位集合异或结果为0或者只有一个位为1（即只有一个字符出现奇数次），那么这两个节点之间的路径可以重排成回文。

时间复杂度: O(n)

空间复杂度: O(n)

from collections import defaultdict


class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        count = defaultdict(int)
        N = len(parent)
        bitset = [None] * N
        ans = 0
        def get_bitset(i):
            if bitset[i] is not None:
                return bitset[i]
            p = parent[i]
            if p == -1:
                b = 0
            else:
                ci = ord(s[i]) - ord('a')
                b = get_bitset(p) ^ (1 << ci)
            bitset[i] = b
            count[b] += 1
            return b

        for i in range(len(parent)):
            get_bitset(i)
        for k, v in count.items():
            ans += v * (v - 1) // 2
            x = k
            while x:
                lowbit = (x & (-x))
                ans += v * count.get(k ^ lowbit, 0)
                x -= lowbit
        return ans

Explore

在DFS过程中，每次访问一个节点时，都会通过该节点的父节点的位集合来更新当前节点的位集合。具体操作是，将父节点的位集合与当前节点字符对应的位进行异或操作。异或操作的特性是，如果某一位是0，则输出与另一个操作数相同的值；如果是1，则输出另一个操作数的相反值。这意味着，如果当前字符在路径上已经出现奇数次（对应位为1），再次出现就会转变为偶数次（1异或1），反之亦然。这样一来，每次迭代都正确地反映了从根节点到当前节点的字符的奇偶次数变化。

异或操作具有几个有用的特性，特别适合于跟踪字符出现次数的奇偶性：1) 自反性，即`x XOR x = 0`，这意味着同一个字符出现两次（偶数次）会抵消自己，导致位回归到0。2) 恒等性，即`x XOR 0 = x`，这意味着字符首次出现时，其对应的位会从0变为1。这两个特性使得异或操作成为更新和记录字符出现奇偶次数的理想选择。

算法通过哈希表统计每种位集合的出现次数，而不是直接记录节点对。在计算可能的回文路径数时，对于每种位集合，都计算选择两个节点（两者位集合相同）的组合数，即`v * (v - 1) / 2`，其中`v`是该位集合的出现次数。通过这种方式，避免了直接对节点对进行双重循环，从而有效减少了重复计算的问题。

在二进制表示中，位集合异或结果为0意味着两个节点的路径上所有字符出现偶数次，可以自由重排成回文。如果异或结果中只有一个位为1，这意味着只有一个字符出现了奇数次，这在回文中也是可接受的（中间字符）。这两种情况都符合回文的条件，因此这种检查方法足以确定两个路径是否可以组成回文。