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

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

<p>Return <em>the number of pairs of nodes </em><code>(u, v)</code><em> such that </em><code>u &lt; v</code><em> and the characters assigned to edges on the path from </em><code>u</code><em> to </em><code>v</code><em> can be <strong>rearranged</strong> to form a <strong>palindrome</strong></em>.</p>

<p>A string is a <strong>palindrome</strong> when it reads the same backwards as forwards.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png" style="width: 281px; height: 181px;" /></p>

<pre>
<strong>Input:</strong> parent = [-1,0,0,1,1,2], s = &quot;acaabc&quot;
<strong>Output:</strong> 8
<strong>Explanation:</strong> The valid pairs are:
- All the pairs (0,1), (0,2), (1,3), (1,4) and (2,5) result in one character which is always a palindrome.
- The pair (2,3) result in the string &quot;aca&quot; which is a palindrome.
- The pair (1,5) result in the string &quot;cac&quot; which is a palindrome.
- The pair (3,5) result in the string &quot;acac&quot; which can be rearranged into the palindrome &quot;acca&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> parent = [-1,0,0,0,0], s = &quot;aaaaa&quot;
<strong>Output:</strong> 10
<strong>Explanation:</strong> Any pair of nodes (u,v) where u &lt; v is valid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == parent.length == s.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= parent[i] &lt;= n - 1</code> for all <code>i &gt;= 1</code></li>
	<li><code>parent[0] == -1</code></li>
	<li><code>parent</code> represents a valid tree.</li>
	<li><code>s</code> consists of only lowercase English letters.</li>
</ul>

from collections import defaultdict, Counter
class Solution:
    def countPalindromePaths(self, parents: List[int], characters: str) -> int:
        # Helper function to perform Depth-First Search (DFS)
        def dfs(node_index: int, xor_value: int):
            # Accessing the variable 'answer' from the outer scope
            nonlocal answer
            for child_index, char_value in adjacency_list[node_index]:
                # Computing the XOR of the current path's characters
                new_xor = xor_value ^ char_value
                # If the XOR matches any of our previous XOR values, it's a palindrome path
                answer += xor_count[new_xor]
                # Check if toggling any single bit (corresponding to changing one character)
                # results in a palindrome path
                for k in range(26):
                    answer += xor_count[new_xor ^ (1 << k)]
                # Count the occurrences of this XOR value along the path
                xor_count[new_xor] += 1
                # Recursive DFS call to continue the search
                dfs(child_index, new_xor)

        # Size of the tree (number of nodes)
        n = len(parents)
        # Adjacency list to represent the tree and store (child_index, binary representation of the character)
        adjacency_list = defaultdict(list)
        for i in range(1, n):
            parent_index = parents[i]
            adjacency_list[parent_index].append((i, 1 << (ord(characters[i]) - ord('a'))))
      
        # The answer to keep track of the number of palindrome paths
        answer = 0
        # Counter to store the number of times an XOR value has been seen on a path
        xor_count = Counter({0: 1})      
        # Start DFS from the root node with XOR value 0 (since no characters have been visited yet)
        dfs(0, 0)      
        # Return the final count of palindrome paths
        return answer

# from collections import defaultdict, Counter
# class Solution:
#     def countPalindromePaths(self, parent: List[int], s: str) -> int:
#         def dfs(i: int, xor: int):
#             nonlocal ans
#             for j, v in g[i]:
#                 x = xor ^ v
#                 ans += cnt[x]
#                 for k in range(26):
#                     ans += cnt[x ^ (1 << k)]
#                 cnt[x] += 1
#                 dfs(j, x)

#         n = len(parent)
#         g = defaultdict(list)
#         for i in range(1, n):
#             p = parent[i]
#             # bitmask  a: 00000, b: 00010, c 00100
#             g[p].append((i, 1 << (ord(s[i]) - ord('a'))))  
#         ans = 0
#         cnt = Counter({0: 1})
#         dfs(0, 0)
#         return ans
76000