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

You are given a tree (i.e. a connected, undirected graph that has no cycles) rooted at node 0 consisting of n nodes numbered from 0 to n - 1. The tree is represented by a 0-indexed array parent of size n, where parent[i] is the parent of node i. Since node 0 is the root, parent[0] == -1.

You are also given a string s of length n, where s[i] is the character assigned to the edge between i and parent[i]. s[0] can be ignored.

Return the number of pairs of nodes (u, v) such that u < v and the characters assigned to edges on the path from u to v can be rearranged to form a palindrome.

A string is a palindrome when it reads the same backwards as forwards.

class Solution {
    void dfs(vector<vector<pair<int,int>>>& adj, int u, long long mask, unordered_map<long long, long long>& freq, unordered_map<long long, long long>& dep, long long& res) {
        if(freq.count(mask)) res += freq[mask];
        if(dep.count(mask)) res += dep[mask] - 1;
        for(int i = 0; i <= 26; i++) {
            if(freq.count(mask ^ (1<<i))) res += freq[mask ^ (1<<i)];
            if(dep.count(mask ^ (1<<i))) res += dep[mask ^ (1<<i)];
        }
        for(auto& [v,m] : adj[u]) {
            dep[mask ^ m] += 1;
            dfs(adj,v,mask ^ m, freq, dep, res);
            dep[mask ^ m] -= 1;
        }
        
        freq[mask] += 1;
    }
public:
    long long countPalindromePaths(vector<int>& parent, string s) {
        int n = parent.size();
        vector<vector<pair<int,int>>> adj(n);
        for(int i = 1; i < parent.size(); i++) {
            adj[parent[i]].push_back({i, 1<<(s[i] - 'a')});
        }
        unordered_map<long long, long long> freq, dep{{0,1}};
        long long res = 0;
        dfs(adj,0,0,freq, dep, res);
        return res;
    }
};