#2791
Count Paths That Can Form a Palindrome in a Tree
candidate master · 1440 · lc hard +32 · verified · 49.5% accepted · 447 likes · top 36%
Description
An undirected tree with n nodes (labeled 0 to n - 1) is rooted at node 0. A 0-indexed array parent of size n encodes it: parent[i] is node i's parent, and parent[0] == -1.
A string s of length n assigns characters to edges: s[i] is the label of the edge between i and its parent. s[0] is unused.
Count all pairs of nodes (u, v) with u < v such that the multiset of edge labels on the path from u to v can be rearranged into a palindrome.
A palindrome reads the same forwards and backwards.
Example 1:
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.
Code
1
2
3