Palindromic paths from a node to the root

A string can be rearranged into a palindrome exactly when at most one letter appears an odd number of times. So we never care about the order of letters on a path, only the parity of each letter's count. With 26 lowercase letters, that parity fits in a 26-bit mask.

Brute force. For each query, walk from the query node up to the root, toggling the bit for each node's letter, and count the steps where the running mask has at most one bit set (m & (m - 1) == 0). That is O(depth) per query, so O(m · n) in the worst case (a path-shaped tree with every node queried). Fine to state first; too slow at n, m = 10^5.

Prefix parity masks. Define pre[u] = XOR of the letter bits on the path from the root down to u, inclusive. For an ancestor v of q, the letters on the path q → v (both ends included) are the letters on root → q minus those on root → parent(v). So the parity mask of that path is

pre[q] XOR pre[parent(v)], with pre[parent(root)] = 0.

Call key(v) = pre[parent(v)]. The answer for q is the number of ancestors v of q (including q) with popcount(pre[q] XOR key(v)) <= 1. That means key(v) equals pre[q] or pre[q] with one bit flipped: 27 candidate masks.

One DFS with a counter. Walk the tree from the root, keeping cnt[mask] = how many nodes on the current root-to-node stack have key == mask. On entering u, add key(u) to the counter (u counts as its own ancestor), then compute

ans[u] = cnt[pre[u]] + sum over b in 0..25 of cnt[pre[u] ^ (1 << b)].

On leaving u, remove key(u). Invariant: while u is being processed, cnt holds exactly the keys of u and its ancestors. Every node's answer is computed once, so queries (including repeats) become lookups.

Two practical points the interviewer will watch for:

• The input is an undirected edge list, so build an adjacency list and orient it by the DFS from node 0 (track the parent, do not assume treeFrom[k] is the parent).
• Trees can be 10^5 deep. Python recursion will overflow, so use an explicit stack with an enter/exit flag.

from collections import defaultdict
from typing import List


def palindromic_ancestor_counts(
    arr: List[str], tree_from: List[int], tree_to: List[int], queries: List[int]
) -> List[int]:
    n = len(arr)
    if n == 0:
        return [0] * len(queries)
    adj: List[List[int]] = [[] for _ in range(n)]
    for a, b in zip(tree_from, tree_to):
        adj[a].append(b)
        adj[b].append(a)

    bit = [1 << (ord(c) - ord("a")) for c in arr]
    flips = [1 << b for b in range(26)]
    pre = [0] * n          # parity mask of root..u
    key = [0] * n          # parity mask of root..parent(u)
    ans = [0] * n
    cnt: defaultdict[int, int] = defaultdict(int)

    # Iterative DFS: (node, parent, exiting?)
    stack = [(0, -1, False)]
    while stack:
        u, p, exiting = stack.pop()
        if exiting:
            cnt[key[u]] -= 1
            continue
        key[u] = pre[p] if p >= 0 else 0
        pre[u] = key[u] ^ bit[u]
        cnt[key[u]] += 1
        m = pre[u]
        total = cnt.get(m, 0)
        for f in flips:
            total += cnt.get(m ^ f, 0)
        ans[u] = total
        stack.append((u, p, True))
        for w in adj[u]:
            if w != p:
                stack.append((w, u, False))

    return [ans[q] for q in queries]


def brute_force(arr, tree_from, tree_to, queries):
    n = len(arr)
    adj = [[] for _ in range(n)]
    for a, b in zip(tree_from, tree_to):
        adj[a].append(b)
        adj[b].append(a)
    parent = [-1] * n
    seen = [False] * n
    seen[0] = True
    order = [0]
    for u in order:
        for w in adj[u]:
            if not seen[w]:
                seen[w] = True
                parent[w] = u
                order.append(w)
    out = []
    for q in queries:
        m, c, v = 0, 0, q
        while v != -1:
            m ^= 1 << (ord(arr[v]) - 97)
            c += m & (m - 1) == 0
            v = parent[v]
        out.append(c)
    return out

• Building the adjacency list: O(n) time and space.
• DFS: each node is pushed and popped twice and does 27 hash lookups, so O(27 · n) = O(n · Σ) time with Σ = 26.
• Queries: O(1) each after the DFS, O(m) total.
• Space: O(n) for masks, answers, the stack and the counter (it holds at most depth-many distinct keys).

• arr = "x", no edges, queries = [0] → [1] (a single letter is a palindrome).
• arr = "aab", edges 0-1, 1-2, queries = [2, 1, 0] → [2, 2, 1]. From node 2: "b" ok, "ba" no (two odd letters), "baa" ok.
• arr = "abc", edges 0-1, 1-2, queries = [2] → [1]: only "c" works; "cb" and "cba" have too many odd letters.
• arr = "abab", path 0-1-2-3, queries = [3] → "b" ok, "ba" no, "bab" ok, "baba" ok → [3].
• Edges given child-first, e.g. tree_from = [1, 2], tree_to = [0, 0], arr = "zzz", queries = [1, 2] → [2, 2] (orientation comes from the root, not the edge order).
• Repeated queries, queries = [3, 3, 3] on the previous path → [3, 3, 3].
• A 10^5-node path of "a" → query at the deepest node returns 10^5; no recursion error.
• Randomized trees checked against brute_force.

1. Paths between any two nodes (count pairs u, v whose path is palindromic). Use pre[u] ^ pre[v] ^ bit[lca], or the simpler trick of storing edge letters on the child so the LCA cancels (LeetCode 2791 style): one global counter of all pre values, still 27 lookups per node, O(26 · n).
2. Online queries for arbitrary (u, ancestor v) pairs. Precompute pre once; each check is popcount(pre[u] ^ key(v)) <= 1 in O(1). Ancestry is checked with Euler tour entry/exit times.
3. Letters change (point updates). Changing a node's letter flips one bit in pre for its whole subtree. Store pre on the Euler tour in a Fenwick tree with XOR (range-XOR, point-query), so each pair check is O(log n). Counting ancestors after updates needs heavier machinery (offline sqrt-decomposition over queries), and it is fair to say so.
4. Return the longest palindromic upward path per query instead of a count. Keep, for each mask, the minimum depth of an ancestor with that key; the answer is depth of q minus the smallest depth among the 27 candidate masks, plus one.
5. Larger alphabet (Unicode). Masks no longer fit in a word. Use random 64-bit hashes per character with XOR (Zobrist hashing); "at most one odd" then means h == 0 or h equals one character's hash, which needs a hash set of the alphabet's hashes, O(Σ) per node or a precomputed set lookup per candidate.

Mid-level (L4)

• States the "at most one odd count" rule and writes the O(depth) brute force correctly.
• Gets to parity bitmasks with a hint and builds the tree from the undirected edge list.
• Produces working code for small inputs.

Senior (L5)

• Derives pre[q] XOR pre[parent(v)] unprompted and handles the "include the query node and the root" boundary cleanly.
• Writes the single DFS with an add/remove counter and the 27-mask lookup, iteratively to avoid recursion limits.
• Gives O(26 · n + m) and tests against a brute force on random trees.

Staff (L6+)

• Generalizes quickly to all-pairs paths and explains why the LCA letter needs care.
• Discusses updates (Euler tour + XOR Fenwick) and what becomes hard (counting under updates).
• Talks about input validation (disconnected input, bad characters) and memory for 10^5–10^6 nodes.