最便宜共同祖先：价格目标不是最低深度

题意与假设

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

• 有限parent树，身份比较不能用price代替；祖先包含本人。
• 并列取B向上遇到的第一个，即共同祖先里更近者；异树无共同祖先返回None。

解题路线

1. 把A到根的所有节点身份放set，再B到根扫描，遇共同节点比较price；不要遇第一个共同节点就返回，它只是LCA。
2. parent循环拒绝。已知同根树的共同祖先为LCA到根整条链，若查询多可先LCA再用路径最小值结构。
3. 只读parent不需要遍历所有children；hA/hB决定基线成本。对象可能有重复价格，set使用id确保不会把不同节点同价误认。

手动走一遍

LCA价格20、其父价格3、根价格8，答案父而非LCA；若A就是B的祖先，仍要比较A及其所有祖先价格。异根即使价格都3也无共同节点。

Python 参考实现

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

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

def cheapest(a,b):
    # Nodes expose parent and price; identities and prices are distinct concepts.
    ancestors=set();u=a
    while u is not None:
        if id(u) in ancestors:raise ValueError("parent cycle")
        ancestors.add(id(u));u=u.parent
    best=None;seen=set();u=b
    while u is not None:
        if id(u) in seen:raise ValueError("parent cycle")
        seen.add(id(u))
        if id(u) in ancestors and (best is None or u.price<best.price):best=u
        u=u.parent
    return best

复杂度

O(hA+hB)时间、O(hA+hB)防环/祖先空间；静态多query可binary lifting加价格min索引O(nlogn)预处理，query O(logn)。

易错点与追问

容易失分的边界

• cheapest与lowest两种目标独立。
• 为优化先找LCA后只返回其price，没有查更高祖先。

继续深挖

• 价格动态更新，怎样用HLD/segment tree查询LCA到根最小？
• 严格祖先不含本人时，A/B父子情形答案怎样改变？