2791. 统计可以形成回文的树中路径数目

Hard

题目描述

给你一个树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。给你一个下标从 0 开始、长度为 n 的数组 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^5
0 <= parent[i] <= n - 1 对所有 i >= 1
parent[0] == -1
parent 表示一棵有效的树。
s 仅由小写英文字母组成。

解题思路

这道题的核心思想是利用位运算来表示字符的奇偶性状态，从而快速判断路径是否能形成回文。

核心观察

一个字符串能重新排列形成回文的充要条件是：最多有一个字符出现奇数次。我们可以用一个26位的掩码来表示每个字符的奇偶性状态，如果某位为1表示对应字符出现奇数次。

算法思路

DFS构建掩码：从根节点开始DFS遍历，计算每个节点到根节点路径上所有字符的奇偶性掩码。
路径掩码计算：对于两个节点u和v，它们之间路径的字符奇偶性掩码等于mask[u] XOR mask[v]。
回文判断：路径能形成回文当且仅当掩码的二进制表示中最多有1个位为1（即掩码为0或为2的幂次）。
统计答案：遍历所有节点，对于每个节点，统计之前访问过的节点中有多少个满足条件。

具体实现

使用哈希表记录每种掩码出现的次数
对于当前节点的掩码mask，需要查找：
- 掩码为mask的节点数（异或后为0，完全匹配）
- 掩码为mask^(1«i)的节点数，其中i∈[0,25]（异或后只有一位不同）

这样可以在O(n)时间内解决问题，避免了O(n²)的暴力枚举。

代码实现

class Solution {
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<int>> children(n);
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].push_back(i);
        }
        
        unordered_map<int, int> maskCount;
        long long result = 0;
        
        function<void(int, int)> dfs = [&](int node, int mask) {
            // 统计当前掩码能形成回文的路径数
            // 情况1: 完全匹配(异或为0)
            if (maskCount.count(mask)) {
                result += maskCount[mask];
            }
            
            // 情况2: 最多一个字符不匹配(异或结果为2的幂次)
            for (int i = 0; i < 26; i++) {
                int targetMask = mask ^ (1 << i);
                if (maskCount.count(targetMask)) {
                    result += maskCount[targetMask];
                }
            }
            
            maskCount[mask]++;
            
            // 递归处理子节点
            for (int child : children[node]) {
                int newMask = mask ^ (1 << (s[child] - 'a'));
                dfs(child, newMask);
            }
        };
        
        dfs(0, 0);
        return result;
    }
};

class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        n = len(parent)
        children = [[] for _ in range(n)]
        
        # 构建邻接表
        for i in range(1, n):
            children[parent[i]].append(i)
        
        mask_count = {}
        result = 0
        
        def dfs(node, mask):
            nonlocal result
            
            # 统计当前掩码能形成回文的路径数
            # 情况1: 完全匹配(异或为0)
            if mask in mask_count:
                result += mask_count[mask]
            
            # 情况2: 最多一个字符不匹配(异或结果为2的幂次)
            for i in range(26):
                target_mask = mask ^ (1 << i)
                if target_mask in mask_count:
                    result += mask_count[target_mask]
            
            mask_count[mask] = mask_count.get(mask, 0) + 1
            
            # 递归处理子节点
            for child in children[node]:
                new_mask = mask ^ (1 << (ord(s[child]) - ord('a')))
                dfs(child, new_mask)
        
        dfs(0, 0)
        return result

public class Solution {
    public long CountPalindromePaths(IList<int> parent, string s) {
        int n = parent.Count;
        List<int>[] children = new List<int>[n];
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        
        // 构建邻接表
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }
        
        Dictionary<int, int> maskCount = new Dictionary<int, int>();
        long result = 0;
        
        void Dfs(int node, int mask) {
            // 统计当前掩码能形成回文的路径数
            // 情况1: 完全匹配(异或为0)
            if (maskCount.ContainsKey(mask)) {
                result += maskCount[mask];
            }
            
            // 情况2: 最多一个字符不匹配(异或结果为2的幂次)
            for (int i = 0; i < 26; i++) {
                int targetMask = mask ^ (1 << i);
                if (maskCount.ContainsKey(targetMask)) {
                    result += maskCount[targetMask];
                }
            }
            
            maskCount[mask] = maskCount.GetValueOrDefault(mask, 0) + 1;
            
            // 递归处理子节点
            foreach (int child in children[node]) {
                int newMask = mask ^ (1 << (s[child] - 'a'));
                Dfs(child, newMask);
            }
        }
        
        Dfs(0, 0);
        return result;
    }
}

var countPalindromePaths = function(parent, s) {
    const n = parent.length;
    const children = Array.from({length: n}, () => []);
    
    // 构建邻接表
    for (let i = 1; i < n; i++) {
        children[parent[i]].push(i);
    }
    
    const maskCount = new Map();
    let result = 0;
    
    function dfs(node, mask) {
        // 统计当前掩码能形成回文的路径数
        // 情况1: 完全匹配(异或为0)
        if (maskCount.has(mask)) {
            result += maskCount.get(mask);
        }
        
        // 情况2: 最多一个字符不匹配(异或结果为2的幂次)
        for (let i = 0; i < 26; i++) {
            const targetMask = mask ^ (1 << i);
            if (maskCount.has(targetMask)) {
                result += maskCount.get(targetMask);
            }
        }
        
        maskCount.set(mask, (maskCount.get(mask) || 0) + 1);
        
        // 递归处理子节点
        for (const child of children[node]) {
            const newMask = mask ^ (1 << (s.charCodeAt(child) - 97));
            dfs(child, newMask);
        }
    }
    
    dfs(0, 0);
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(n × 26) = O(n)
空间复杂度	O(n)

时间复杂度：每个节点访问一次，每次需要检查26个可能的掩码组合，总体为O(n)
空间复杂度：需要存储每个掩码的出现次数，最坏情况下有O(n)种不同的掩码；递归调用栈深度最大为O(n)

题目描述#

解题思路#

核心观察#

算法思路#

具体实现#

代码实现#

复杂度分析#

相关题目#