↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

LeetCode-2791 树中可以形成回文的路径数 #

Solution1 #

允许路径上的字符重新排列后组成回文串, 因此我们只关心路径上字符的数量, 更准确地说是只关心字符数量的奇偶性, 通过状态压缩可以用一个数代表一条路径的字符状态 (不妨用 $xor$ 来表示, 可以发现路径的拼接和裁剪相当于作异或操作) . 考虑从 $A$ 到 $B$ 的路径值 $xor(A, B)$ 可以表示为两条路径的异或和 $xor(LCA(A, B), A) \oplus xor(LCA(A, B), B)$ ; 进一步地, 将 $xor(LCA(A,B), A)$ 表示成 $xor(0, LCA(A, B)) \oplus xor(0, A)$ , 同样处理 $xor(LCA(A,B), B)$ , 则有 $$xor(A, B) \= xor(0, LCA(A, B)) \oplus xor(0, A) \oplus xor(0, LCA(A, B)) \oplus xor(0, B) \= xor(0, A) + xor(0, B) $$ 故在深度优先搜索计算异或值时计数即可.

using ll = long long;
class Solution {
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        int n = parent.size();
        ll ans = 0;
        vector<pair<int, int>> e[n];
        for (int i = 1; i < n; i++) {
            e[parent[i]].emplace_back(i, 1 << (s[i] - 'a'));
        }
        unordered_map<int, int> cnt;
        function<void(int, int)> dfs = [&](int x, int xor_x) {
            ans += cnt[xor_x];
            for (int i = 0; i < 26; i++) {
                ans += cnt[xor_x ^ (1 << i)];
            }
            cnt[xor_x]++;
            for (auto y : e[x]) {
                dfs(y.first, xor_x ^ y.second);
            }
        }; 
        dfs(0, 0);
        return ans;
    }
};