Count Paths That Can Form a Palindrome in a Tree solution and explanation

from collections import defaultdict

def countPalindromePaths(parent, s):
    def dfs(node, path):
        nonlocal count
        path ^= 1 << (ord(s[node]) - ord('a'))
        count += memo[path]
        for i in range(26):
            count += memo[path ^ (1 << i)]
        memo[path] += 1
        for child in tree[node]:
            dfs(child, path)
        memo[path] -= 1

    tree = defaultdict(list)
    for child, par in enumerate(parent):
        if par != -1:
            tree[par].append(child)

    memo = defaultdict(int)
    count = 0
    dfs(0, 0)
    return count

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    int countPalindromePaths(vector<int>& parent, string s) {
        vector<vector<int>> tree(parent.size());
        for (int i = 1; i < parent.size(); ++i) {
            tree[parent[i]].push_back(i);
        }

        unordered_map<int, int> memo;
        int count = 0;

        function<void(int, int)> dfs = [&](int node, int path) {
            path ^= 1 << (s[node] - 'a');
            count += memo[path];
            for (int i = 0; i < 26; ++i) {
                count += memo[path ^ (1 << i)];
            }
            ++memo[path];
            for (int child : tree[node]) {
                dfs(child, path);
            }
            --memo[path];
        };

        memo[0] = 1;
        dfs(0, 0);
        return count;
    }
};

import java.util.*;

class Solution {
    public int countPalindromePaths(int[] parent, String s) {
        Map<Integer, List<Integer>> tree = new HashMap<>();
        for (int i = 1; i < parent.length; i++) {
            tree.computeIfAbsent(parent[i], k -> new ArrayList<>()).add(i);
        }

        int[] dp = new int[s.length()];
        int[] freq = new int[26];
        Arrays.fill(dp, -1);
        dp[0] = pathToMask(0, s, freq, tree);

        return countPairsWithMask(dp);
    }

    private int pathToMask(int node, String s, int[] freq, Map<Integer, List<Integer>> tree) {
        int mask = 0;
        for (char c : s.toCharArray()) {
            mask ^= (1 << (c - 'a'));
        }
        if (tree.containsKey(node)) {
            for (int child : tree.get(node)) {
                pathToMask(child, s, freq, tree);
            }
        }
        return mask;
    }

    private int countPairsWithMask(int[] masks) {
        int count = 0;
        Map<Integer, Integer> maskCount = new HashMap<>();
        for (int mask : masks) {
            count += maskCount.getOrDefault(mask, 0);
            for (int i = 0; i < 26; i++) {
                count += maskCount.getOrDefault(mask ^ (1 << i), 0);
            }
            maskCount.put(mask, maskCount.getOrDefault(mask, 0) + 1);
        }
        return count;
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    public int CountPalindromePaths(int[] parent, string s) {
        var tree = new Dictionary<int, List<int>>();
        for (int i = 1; i < parent.Length; i++) {
            if (!tree.ContainsKey(parent[i])) {
                tree[parent[i]] = new List<int>();
            }
            tree[parent[i]].Add(i);
        }

        int[] dp = new int[s.Length];
        int[] freq = new int[26];
        Array.Fill(dp, -1);
        dp[0] = PathToMask(0, s, freq, tree);

        return CountPairsWithMask(dp);
    }

    private int PathToMask(int node, string s, int[] freq, Dictionary<int, List<int>> tree) {
        int mask = 0;
        foreach (char c in s.ToCharArray()) {
            mask ^= (1 << (c - 'a'));
        }
        if (tree.ContainsKey(node)) {
            foreach (int child in tree[node]) {
                PathToMask(child, s, freq, tree);
            }
        }
        return mask;
    }

    private int CountPairsWithMask(int[] masks) {
        int count = 0;
        var maskCount = new Dictionary<int, int>();
        foreach (int mask in masks) {
            count += maskCount.GetValueOrDefault(mask);
            for (int i = 0; i < 26; i++) {
                count += maskCount.GetValueOrDefault(mask ^ (1 << i));
            }
            if (!maskCount.ContainsKey(mask)) {
                maskCount[mask] = 0;
            }
            maskCount[mask]++;
        }
        return count;
    }
}

function countPalindromePaths(parent: number[], s: string): number {
    const n = parent.length;
    const g: [number, number][][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push([i, 1 << (s.charCodeAt(i) - 97)]);
    }
    const cnt: Map<number, number> = new Map();
    cnt.set(0, 1);
    let ans = 0;
    const dfs = (i: number, xor: number): void => {
        for (const [j, v] of g[i]) {
            const x = xor ^ v;
            ans += cnt.get(x) || 0;
            for (let k = 0; k < 26; ++k) {
                ans += cnt.get(x ^ (1 << k)) || 0;
            }
            cnt.set(x, (cnt.get(x) || 0) + 1);
            dfs(j, x);
        }
    };
    dfs(0, 0);
    return ans;
}

func countPalindromePaths(parent []int, s string) (ans int64) {
	type pair struct{ i, v int }
	n := len(parent)
	g := make([][]pair, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		g[p] = append(g[p], pair{i, 1 << (s[i] - 'a')})
	}
	cnt := map[int]int{0: 1}
	var dfs func(i, xor int)
	dfs = func(i, xor int) {
		for _, e := range g[i] {
			x := xor ^ e.v
			ans += int64(cnt[x])
			for k := 0; k < 26; k++ {
				ans += int64(cnt[x^(1<<k)])
			}
			cnt[x]++
			dfs(e.i, x)
		}
	}
	dfs(0, 0)
	return
}