A storage system is organised as a tree of n nodes numbered 0 to n - 1, with node 0 as the root. Every node holds one lowercase letter. For a node u, look at its ancestors one by one, starting with u itself and moving up to the root. For each such ancestor v, take the letters on the path from u up to v (both ends included). Call v good for u if those letters can be rearranged into a palindrome.
Write count_palindromic_paths(labels: str, edges: list[tuple[int, int]], queries: list[int]) -> list[int]:
labels[i]is the letter at nodei;n = len(labels).edgesholds then - 1undirected edges of the tree, each a pair(x, y)in any order.- For each node
uinqueries, answer with the number of nodesvon the path fromuto the root that are good foru. Return the answers in the order ofqueries. Nodes may be queried more than once.
v = u is always good (one letter is a palindrome), so every answer is at least 1.
# 0 a
# / \
# 1 b 2 a
# | |
# 3 b 4 c
count_palindromic_paths("ababc", [(0, 1), (0, 2), (1, 3), (4, 2)], [3, 4, 2, 0]) # [3, 2, 2, 1]
- Node
3: the paths areb(good),bb(good) andbba(rearranges tobab, good): 3. - Node
4:c(good),ca(no),caa(rearranges toaca, good): 2. - Node
2:aandaa: 2. Node0: justa: 1.
Constraints: 1 <= n <= 10^5, 1 <= len(queries) <= 10^5. The tree can be a single chain 10^5 nodes deep, so walking from every query to the root is far too slow, and so is deep recursion.
Show hint
letters can form a palindrome exactly when at most one letter appears an odd number of times. Let mask(x) be the XOR of 1 << letter over the root-to-x path, with mask of "above the root" equal to 0. The letters from u up to v have parity mask(u) ^ mask(parent(v)), which must be 0 or a single bit. Do one iterative DFS keeping a counter of mask(parent(v)) for every v on the current root path, and look up the 27 allowed values when you are at u.