Count Palindromic Ancestor Paths

Problem Statement

You are given a rooted tree with N nodes, indexed 0 to N-1. Each node i has an associated lowercase English character c_i. A path from the root to any node u defines a sequence of characters. A path is "palindrome-permutable" if the characters along that path can be rearranged to form a palindrome.

Given the tree structure and a list of queries, determine for each node u whether the path from the root to u can form a palindrome. A set of characters can form a palindrome if and only if at most one character appears an odd number of times.

Implement the function: def solve(n, edges, chars):

• n: An integer representing the number of nodes.
• edges: A list of tuples (u, v) representing directed edges from parent u to child v.
• chars: A string where chars[i] is the character at node i.

Return a list of booleans of length n, where the i-th element is True if the path from the root to node i can form a palindrome, and False otherwise.

Constraints

• 1 <= N <= 10^5
• chars contains only lowercase 'a'-'z'.

Examples

Example 1

Input: n = 3, edges = [(0, 1), (1, 2)], chars = "aba" Output: [True, True, True] Explanation:

• Node 0: "a" (Odd count: 'a':1. Valid.)
• Node 1: "ab" (Odd counts: 'a':1, 'b':1. Invalid.) -> Wait, "ab" cannot form a palindrome. Let's re-check: 'a'=1, 'b'=1. Two odd counts. False.
• Correction: The example path "aba" is True. The path "ab" is False.

Example 2

Input: n = 2, edges = [(0, 1)], chars = "aa" Output: [True, True] Explanation:

• Node 0: "a" (True)
• Node 1: "aa" (True)