Uber 树上回文路径：节点字符与祖先终点查询

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入是 n 个节点的无向树，固定以节点 0 为根，每个节点恰有一个小写英文字母；查询给出起始节点 u。
• 每个候选终点 v 必须是 u 的祖先（含 u）。若 u→v 的节点字符多重集可重排为回文，就将 v 计入答案。
• 回文是‘可以重新排列’，不是沿原路径顺序已经回文；当且仅当最多一种字符出现奇数次。

解题路线

1. 对根到当前节点的字符奇偶性做 26 位 XOR 掩码。路径 u→v（含 v）的掩码等于 prefix[u] XOR prefix[parent(v)]。
2. 在 DFS 走到 u 之前，用活跃哈希表存当前祖先链上每个 prefix[parent(v)] 的频数，包含根的虚拟父前缀 0。答案是 active[prefix[u]] 加上 26 个只差一位的 active 值。
3. 计算 u 的答案后把 prefix[u] 放进 active 供子节点使用；离开 u 子树时撤销，防止其他分支的节点被误当作祖先。代码用显式进出栈避免深树递归溢出。

手动走一遍

树 0(z)→1(a)→3(a) 且 0→2(a)，查询 u=3：到 3 的路径 a、到 1 的 aa、到 0 的 aaz 都可重排为回文，答案 3。节点 2 不在 3 的祖先链上，不能计数。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Count ancestor-ending paths whose node letters can form a palindrome."""

from collections import defaultdict


def count_palindromic_ancestor_paths(
    letters: str, edges: list[tuple[int, int]], queries: list[int]
) -> list[int]:
    n = len(letters)
    if n == 0 or len(edges) != n - 1 or any(not "a" <= ch <= "z" for ch in letters):
        raise ValueError("expected a nonempty tree with lowercase node letters")
    graph = [[] for _ in range(n)]
    for a, b in edges:
        if not (0 <= a < n and 0 <= b < n) or a == b:
            raise ValueError("invalid edge")
        graph[a].append(b)
        graph[b].append(a)
    if any(not 0 <= q < n for q in queries):
        raise ValueError("invalid query node")

    answer = [0] * n
    active = defaultdict(int, {0: 1})  # prefix before the root
    seen = set()
    stack = [(0, -1, 0, False)]  # node, parent, prefix before node, exit flag
    while stack:
        node, parent, incoming_mask, exiting = stack.pop()
        mask = incoming_mask ^ (1 << (ord(letters[node]) - ord("a")))
        if exiting:
            active[mask] -= 1
            if active[mask] == 0:
                del active[mask]
            continue
        if node in seen:
            raise ValueError("edges contain a cycle")
        seen.add(node)
        answer[node] = active.get(mask, 0) + sum(active.get(mask ^ (1 << bit), 0) for bit in range(26))
        active[mask] += 1
        stack.append((node, parent, incoming_mask, True))
        for neighbor in graph[node]:
            if neighbor != parent:
                stack.append((neighbor, node, mask, False))
    if len(seen) != n:
        raise ValueError("tree is disconnected")
    return [answer[node] for node in queries]

复杂度

每个节点进入时查 27 个掩码，时间 O(26n+q)，建图 O(n)，空间 O(n+q)（邻接表、遍历栈、答案与当前路径前缀）。若字母表大小为 σ，则 O(σn+q)。

易错点与追问

容易失分的边界

• 套用‘边上字符、任意两节点配对’的 LC2791 模板会错：此题字符在节点上，且只数查询节点到其祖先的路径。
• 区间掩码要异或 prefix[parent(v)]，不是 prefix[v]，否则会把祖先 v 的字符漏掉。
• DFS 返回时必须移走当前前缀；否则兄弟子树的节点也会被计入同一查询的候选祖先。

继续深挖

• 若只查询一个节点，沿其到根的路径直接更新字符奇偶并逐个检查，时间 O(路径长度)，无需全树预处理。
• 若节点字符可动态修改，所有后代前缀都会改变，静态 DFS 答案不能直接复用；需要先明确更新/查询比例再设计重算或树分解方案。