Palindromic paths from a node to the root

A storage system keeps its directories in a tree. Each directory holds one lowercase letter as a label. You are given:

• arr: a list of n lowercase letters; arr[i] is the label of node i. Nodes are numbered 0 to n - 1, and node 0 is the root.
• tree_from and tree_to: two lists of length n - 1. Edge k connects tree_from[k] and tree_to[k]. Edges are undirected; either end may be the parent.
• queries: a list of m node ids.

For a query node q, look at every node v on the path from q up to the root, including q and the root. Call v good if the labels on the path from q to v (both ends included) can be rearranged into a palindrome.

Return a list where entry i is the number of good nodes for queries[i].

def palindromic_ancestor_counts(
    arr: list[str], tree_from: list[int], tree_to: list[int], queries: list[int]
) -> list[int]: ...

Constraints

• 1 <= n <= 10^5, 1 <= m <= 10^5
• The edges form a tree; queries may repeat.
• The tree can be a single long chain.

Example 1

arr       = ['c', 'd', 'd', 'c']
tree_from = [0, 1, 1]
tree_to   = [1, 2, 3]
queries   = [2, 3]
output    = [3, 2]

Node 2 ('d'): "d", "dd", "ddc" all rearrange into palindromes, so 3. Node 3 ('c'): "c" works, "cd" does not, "cdc" works, so 2.

Example 2

arr       = ['a', 'a', 'b']
tree_from = [1, 2]
tree_to   = [0, 1]
queries   = [2, 0]
output    = [2, 1]

The edges are listed child-first. From node 2: "b" and "baa" work; "ba" does not.