Apple Unit Conversion II：树上换算、模逆与任意两单位查询

题意与假设

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

• 训练版采用标准题的 n 个单位 0…n−1、n−1 条由父指向子且从 0 可达的倍率边，以及任意有向单位对查询。1 个父单位等于 factor 个子单位，结果取模 1,000,000,007。
• factor 必须为非零模数余数，才能做模逆；题目没有说面试是否改成浮点、仿射或多家族换算，后者分别需要不同模型。

解题路线

1. 构建父到子邻接表，从 0 遍历，计算 P[u]：1 个单位 0 对应多少单位 u。因是树，每个节点唯一父路径；遍历同时检测环、重父和不可达。
2. 把 1 个 source 换到 target：P[target]/P[source]。在质数模数下对非零 P[source] 用费马小定理求逆，答案是 P[target]×P[source]^(MOD−2) mod MOD。
3. 预处理所有节点比例与模逆后，每条查询只做一次乘法；若查询很少，也可按需求逆减少预处理成本。
4. q10 的温度类转换是 y=ax+b，不能只用比值；多家族、不一致环也都不满足本题树结构。

手动走一遍

边 0→1 倍率 2、0→2 倍率 6，则 P=[1,2,6]。1→2 得 6/2=3；1→0 得 1/2 mod 1,000,000,007，即 500000004。

Python 参考实现

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

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

from collections import deque

MOD = 1_000_000_007


def conversion_results(
    n: int, conversions: list[tuple[int, int, int]], queries: list[tuple[int, int]]
) -> list[int]:
    """Tree conversions: 1 parent unit = factor child units, modulo MOD."""
    if n <= 0 or len(conversions) != n - 1:
        raise ValueError("expected a nonempty conversion tree")
    children: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for parent, child, factor in conversions:
        if not (0 <= parent < n and 0 <= child < n and 0 < factor < MOD):
            raise ValueError("invalid conversion")
        children[parent].append((child, factor))

    from_root = [0] * n
    from_root[0] = 1
    queue = deque([0])
    while queue:
        parent = queue.popleft()
        for child, factor in children[parent]:
            if from_root[child]:
                raise ValueError("cycle or duplicate child")
            from_root[child] = from_root[parent] * factor % MOD
            queue.append(child)
    if not all(from_root):
        raise ValueError("disconnected tree")

    inverse = [pow(value, MOD - 2, MOD) for value in from_root]
    result = []
    for source, target in queries:
        if not (0 <= source < n and 0 <= target < n):
            raise ValueError("unknown unit")
        result.append(from_root[target] * inverse[source] % MOD)
    return result

复杂度

建图与遍历 O(n)，对每个点求模逆 O(n log MOD)，q 次查询 O(q)，空间 O(n+q)（含答案）。若只有少量查询，可把求逆延后。

易错点与追问

容易失分的边界

• 把 Unit Conversion II 与 q10 的仿射/多家族题合并。
• 直接做整数除法或浮点相除后取模。
• 漏掉转换方向，把 P[source]/P[target] 倒置。
• 没有验证因子可逆却调用模逆。
• 把树题的解法用于有环且倍率矛盾的输入。

继续深挖

• 如果 factor 可被 MOD 整除，模逆为何不存在？
• 若有多条查询且需要在线增加叶子，如何更新比例？
• 加入有环转换时怎样发现矛盾？
• 若转换包含温度偏移，公式如何改？