树中可以形成回文的路径数-526互联

找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以重新排列形成回文的所有节点对 (u, v) ，并返回节点对的数目。
如果一个字符串正着读和反着读都相同，那么这个字符串就是一个回文

1. 二进制状态压缩 + 深度优先搜索 + 哈希

class Solution {
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        //重新排列形成回文串，表示奇数次的字符最多存在一个
        //首先根据静态索引构建树，这里直接建图
        int n = parent.size();
        vector<vector<int>> graph(n);
        for(int i=1;i<n;i++)
            graph[parent[i]].push_back(i);//只存储每个顶点的后继
        long long res = 0;
        unordered_map<int,int> m;//记录根节点到子节点路径状态个数
        m[0] = 1;
        function<void(int,int)> dfs = [&](int v,int mask){//由于我们只需知道每个字符个数的奇偶性，这里直接用26位的二进制数记录
            for(auto u:graph[v]){
                int bit = 1<<(s[u]-'a');//记录当前字符
                int x = mask^bit;
                res+=m[x];//相同状态的字符串路径，与该路径之间，必然存在一条回文，该回文没有奇数次字符
                for(int i=0;i<26;i++)//满足一个奇数次字符的路径
                    res+=m[x^(1<<i)];
                m[x]++;
                dfs(u,x);
            }
        };
        dfs(0,0);//从初始节点开始，
        return res;
    }
};

回文