You have a tree whose nodes are numbered from 0 through n - 1. It is described by a parent array parent, with parent[0] = -1 and parent[i] identifying the parent of node i for every i > 0.
A string s of length n assigns a lowercase letter to each edge connecting node i with parent[i]. Because node 0 is the root and has no parent edge, the value of s[0] does not matter.
For each pair of different nodes u and v, examine the letters on the unique path connecting them. Count the unordered pairs for which those letters can be rearranged to produce a palindrome.
Return that count.
Example 1:
Input: parent = [-1,0,0,1,1,2], s = "acaabc"
Output: 8
Explanation: The qualifying pairs are (0,1), (0,2), (1,3), (1,4), (1,5), (2,3), (2,5), and (3,5). In every one of these paths, no more than one character occurs an odd number of times.
Example 2:
Input: parent = [-1,0,0,0,0], s = "aaaaa"
Output: 10
Explanation: All paths contain only the letter a, so every pair of distinct nodes satisfies the palindrome condition.
Example 3:
Input: parent = [-1,0,1], s = "abc"
Output: 2
Explanation: (0,1) and (1,2) qualify. The path from 0 to 2 contains b and c, whose frequencies cannot be rearranged into a palindrome.
1 <= parent.length == s.length <= 10^5parent[0] == -10 <= parent[i] < parent.length for i > 0parent describes a valid trees contains only lowercase English letters