Algorithms
Hard
2791
2905
Count Paths That Can Form a Palindrome in a Tree
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.

Example 1:

[https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png]

Input: parent = [-1,0,0,1,1,2], s = "acaabc"
Output: 8
Explanation: 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 "aca" which is a palindrome.
- The pair (1,5) result in the string "cac" which is a palindrome.
- The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca".

Example 2:

Input: parent = [-1,0,0,0,0], s = "aaaaa"
Output: 10
Explanation: Any pair of nodes (u,v) where u < v is valid.


Constraints:

 * n == parent.length == s.length
 * 1 <= n <= 105
 * 0 <= parent[i] <= n - 1 for all i >= 1
 * parent[0] == -1
 * parent represents a valid tree.
 * s consists of only lowercase English letters.
"""
class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        
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.

Example 1:

[https://assets.leetcode.com/uploads/2023/07/15/treedrawio-8drawio.png]

Input: parent = [-1,0,0,1,1,2], s = "acaabc"
Output: 8
Explanation: 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 "aca" which is a palindrome.
- The pair (1,5) result in the string "cac" which is a palindrome.
- The pair (3,5) result in the string "acac" which can be rearranged into the palindrome "acca".

Example 2:

Input: parent = [-1,0,0,0,0], s = "aaaaa"
Output: 10
Explanation: Any pair of nodes (u,v) where u < v is valid.


Constraints:

 * n == parent.length == s.length
 * 1 <= n <= 105
 * 0 <= parent[i] <= n - 1 for all i >= 1
 * parent[0] == -1
 * parent represents a valid tree.
 * s consists of only lowercase English letters.


Please complete the code below to solve above prblem:
```python
class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        
```

my_solution = Solution()

test_input = { "parent": [-1,0,0,1,1,2], "s": "acaabc" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,0,0,0,0], "s": "aaaaa" }
assert my_solution.countPalindromePaths(**test_input) == 10

test_input = { "parent": [-1,0], "s": "pi" }
assert my_solution.countPalindromePaths(**test_input) == 1

test_input = { "parent": [-1,5,0,5,5,2], "s": "xsbcqq" }
assert my_solution.countPalindromePaths(**test_input) == 7

test_input = { "parent": [-1,6,8,5,0,4,2,0,4], "s": "tiaiaivea" }
assert my_solution.countPalindromePaths(**test_input) == 20

test_input = { "parent": [-1,0,0,0,1,3,7,2], "s": "pxxgtgpp" }
assert my_solution.countPalindromePaths(**test_input) == 18

test_input = { "parent": [-1,0,1,4,1,0], "s": "hfhmmf" }
assert my_solution.countPalindromePaths(**test_input) == 12

test_input = { "parent": [-1,0,1], "s": "cri" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,0,5,7,0,0,1,2,0], "s": "snlzlzngna" }
assert my_solution.countPalindromePaths(**test_input) == 19

test_input = { "parent": [-1,0,0], "s": "sat" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0], "s": "ko" }
assert my_solution.countPalindromePaths(**test_input) == 1

test_input = { "parent": [-1,0,6,4,1,6,3,1], "s": "jibwrfoi" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,4,0,4,6,0,5,5], "s": "bhrlorou" }
assert my_solution.countPalindromePaths(**test_input) == 18

test_input = { "parent": [-1,4,4,6,0,7,1,1], "s": "boqvndoo" }
assert my_solution.countPalindromePaths(**test_input) == 18

test_input = { "parent": [-1,2,0,1,0], "s": "eixnx" }
assert my_solution.countPalindromePaths(**test_input) == 6

test_input = { "parent": [-1,5,0,2,2,3], "s": "jwlllw" }
assert my_solution.countPalindromePaths(**test_input) == 14

test_input = { "parent": [-1,2,6,2,5,2,7,0], "s": "pipfippl" }
assert my_solution.countPalindromePaths(**test_input) == 15

test_input = { "parent": [-1,6,0,6,5,6,2,6,5,6], "s": "zwrdhnhwtf" }
assert my_solution.countPalindromePaths(**test_input) == 11

test_input = { "parent": [-1,4,1,1,5,0], "s": "gndfnj" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,0,0,0,1], "s": "crwkr" }
assert my_solution.countPalindromePaths(**test_input) == 7

test_input = { "parent": [-1,4,4,4,0,2,0], "s": "wwwwewd" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,2,0], "s": "mwz" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,1,6,5,0,1,1,1,0], "s": "mqgmjzrwuq" }
assert my_solution.countPalindromePaths(**test_input) == 14

test_input = { "parent": [-1,2,3,0,3,3,3,3], "s": "bnievjov" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,0,0], "s": "kyr" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,5,1,2,3,2,3,9,4], "s": "xukzwzsnww" }
assert my_solution.countPalindromePaths(**test_input) == 18

test_input = { "parent": [-1,6,0,1,5,0,2,2,6,0], "s": "snlpzocqpt" }
assert my_solution.countPalindromePaths(**test_input) == 10

test_input = { "parent": [-1,3,0,5,5,2], "s": "pxlxpl" }
assert my_solution.countPalindromePaths(**test_input) == 12

test_input = { "parent": [-1,5,5,5,5,0], "s": "ketewj" }
assert my_solution.countPalindromePaths(**test_input) == 6

test_input = { "parent": [-1,0,4,0,0], "s": "zrrqq" }
assert my_solution.countPalindromePaths(**test_input) == 7

test_input = { "parent": [-1,0,0], "s": "qlw" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,0], "s": "bds" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,2,6,6,0,4,4,2], "s": "odggsrsp" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,0,1], "s": "ldk" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,7,0,6,2,3,3,3], "s": "elllffflv" }
assert my_solution.countPalindromePaths(**test_input) == 28

test_input = { "parent": [-1,4,4,0,0], "s": "ntzhc" }
assert my_solution.countPalindromePaths(**test_input) == 4

test_input = { "parent": [-1,5,4,1,1,0,4], "s": "gmcmavf" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,0,0,4,0], "s": "aogkg" }
assert my_solution.countPalindromePaths(**test_input) == 6

test_input = { "parent": [-1,2,0], "s": "xmt" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,2,0], "s": "dff" }
assert my_solution.countPalindromePaths(**test_input) == 3

test_input = { "parent": [-1,0,1,1], "s": "lsvw" }
assert my_solution.countPalindromePaths(**test_input) == 3

test_input = { "parent": [-1,0,0], "s": "ovi" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,6,0,5,2,2,0,3], "s": "lpnfznpf" }
assert my_solution.countPalindromePaths(**test_input) == 19

test_input = { "parent": [-1,7,5,5,0,0,2,2], "s": "hqitxxwi" }
assert my_solution.countPalindromePaths(**test_input) == 16

test_input = { "parent": [-1,2,0], "s": "pyw" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,0,0], "s": "ybfa" }
assert my_solution.countPalindromePaths(**test_input) == 3

test_input = { "parent": [-1,3,6,6,6,0,0,4], "s": "ulicllkc" }
assert my_solution.countPalindromePaths(**test_input) == 11

test_input = { "parent": [-1,3,1,0], "s": "ukne" }
assert my_solution.countPalindromePaths(**test_input) == 3

test_input = { "parent": [-1,2,0,1,0,0], "s": "rhlxdd" }
assert my_solution.countPalindromePaths(**test_input) == 6

test_input = { "parent": [-1,4,5,0,2,0], "s": "zenbnb" }
assert my_solution.countPalindromePaths(**test_input) == 12

test_input = { "parent": [-1,0,5,4,5,1,3,9,7,4], "s": "jigognjnlb" }
assert my_solution.countPalindromePaths(**test_input) == 12

test_input = { "parent": [-1,4,4,6,3,0,5,3,6], "s": "imrcmdkew" }
assert my_solution.countPalindromePaths(**test_input) == 11

test_input = { "parent": [-1,4,4,0,6,4,0,0], "s": "dqpipiyz" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,0,0], "s": "mgm" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,4,0,1], "s": "pzlob" }
assert my_solution.countPalindromePaths(**test_input) == 4

test_input = { "parent": [-1,8,0,8,8,3,4,4,0,6], "s": "vvbvyovyvy" }
assert my_solution.countPalindromePaths(**test_input) == 30

test_input = { "parent": [-1,0,4,0,5,1,1], "s": "dvrvpea" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,0,1], "s": "jnx" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0,1,2], "s": "wxjj" }
assert my_solution.countPalindromePaths(**test_input) == 5

test_input = { "parent": [-1,3,3,0,1,2,1], "s": "erorchx" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,0,4,1,1,4,3], "s": "ywzwzcw" }
assert my_solution.countPalindromePaths(**test_input) == 14

test_input = { "parent": [-1,4,6,2,3,3,0], "s": "bititzq" }
assert my_solution.countPalindromePaths(**test_input) == 10

test_input = { "parent": [-1,2,0], "s": "uup" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,2,3,0,0], "s": "siiou" }
assert my_solution.countPalindromePaths(**test_input) == 6

test_input = { "parent": [-1,2,0,2,0], "s": "dilfs" }
assert my_solution.countPalindromePaths(**test_input) == 4

test_input = { "parent": [-1,3,7,0,1,0,2,3,0], "s": "wqojvjoqq" }
assert my_solution.countPalindromePaths(**test_input) == 22

test_input = { "parent": [-1,0], "s": "hi" }
assert my_solution.countPalindromePaths(**test_input) == 1

test_input = { "parent": [-1,3,1,4,0,6,3,1], "s": "fwvwwqqw" }
assert my_solution.countPalindromePaths(**test_input) == 21

test_input = { "parent": [-1,0,4,2,1,1,1], "s": "hkmmkmk" }
assert my_solution.countPalindromePaths(**test_input) == 16

test_input = { "parent": [-1,4,3,1,0], "s": "bzeez" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,3,3,0], "s": "zyuj" }
assert my_solution.countPalindromePaths(**test_input) == 3

test_input = { "parent": [-1,0,1,4,6,2,2], "s": "tlcpcll" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,2,0], "s": "vjw" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,0], "s": "nz" }
assert my_solution.countPalindromePaths(**test_input) == 1

test_input = { "parent": [-1,0,0], "s": "iot" }
assert my_solution.countPalindromePaths(**test_input) == 2

test_input = { "parent": [-1,2,8,8,3,1,2,0,0], "s": "rlurrluxm" }
assert my_solution.countPalindromePaths(**test_input) == 19

test_input = { "parent": [-1,5,0,0,0,4], "s": "zxrddx" }
assert my_solution.countPalindromePaths(**test_input) == 10

test_input = { "parent": [-1,0,1,2], "s": "tffc" }
assert my_solution.countPalindromePaths(**test_input) == 5

test_input = { "parent": [-1,5,3,0,3,0], "s": "ltdewr" }
assert my_solution.countPalindromePaths(**test_input) == 5

test_input = { "parent": [-1,0,4,5,0,1], "s": "gjwwjv" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,7,7,0,8,2,2,4,3,8], "s": "cnssgsoogy" }
assert my_solution.countPalindromePaths(**test_input) == 20

test_input = { "parent": [-1,7,1,6,0,0,7,0], "s": "zaceoxax" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,0,1,0,3,0], "s": "zrvyyc" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,4,9,0,3,3,7,4,2,0], "s": "qxixxxxxix" }
assert my_solution.countPalindromePaths(**test_input) == 41

test_input = { "parent": [-1,2,0,5,5,2,5], "s": "hoptvuu" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,7,3,0,3,1,0,3], "s": "kopflpao" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,0,1,6,1,1,1], "s": "bhhslhl" }
assert my_solution.countPalindromePaths(**test_input) == 11

test_input = { "parent": [-1,0,0,1,2], "s": "khhch" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,0,3,0], "s": "koss" }
assert my_solution.countPalindromePaths(**test_input) == 5

test_input = { "parent": [-1,3,4,4,0], "s": "owzoq" }
assert my_solution.countPalindromePaths(**test_input) == 4

test_input = { "parent": [-1,2,0,1,1], "s": "zqqww" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,0,1,1,1,2,2], "s": "lacccdb" }
assert my_solution.countPalindromePaths(**test_input) == 13

test_input = { "parent": [-1,4,3,4,6,6,7,0,6], "s": "sjoooorrm" }
assert my_solution.countPalindromePaths(**test_input) == 24

test_input = { "parent": [-1,7,4,2,0,6,2,3,7], "s": "guqyxxtau" }
assert my_solution.countPalindromePaths(**test_input) == 9

test_input = { "parent": [-1,4,4,0,0], "s": "scicc" }
assert my_solution.countPalindromePaths(**test_input) == 8

test_input = { "parent": [-1,5,8,6,3,0,2,3,1], "s": "naphhahhp" }
assert my_solution.countPalindromePaths(**test_input) == 29

test_input = { "parent": [-1,3,8,8,5,0,4,0,0,2], "s": "ciiyggofij" }
assert my_solution.countPalindromePaths(**test_input) == 23

test_input = { "parent": [-1,2,0,2,2,3,7,8,4,2], "s": "stthtthddt" }
assert my_solution.countPalindromePaths(**test_input) == 34

test_input = { "parent": [-1,2,0,7,3,7,4,0], "s": "mjjsjdsj" }
assert my_solution.countPalindromePaths(**test_input) == 18

test_input = { "parent": [-1,0], "s": "ey" }
assert my_solution.countPalindromePaths(**test_input) == 1