树上访问任务并到终点：最小子树双走减去起终路径

题意与假设

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

• 无向连通树、非负边长，从s出发最后在t，需经过所有task，允许重复边。
• 只求距离；输入节点0..n−1，任务为可重遍历集合/列表。含有环的一般图不适用该树公式。

解题路线

1. 从s根遍历记录parent与根距离，自底向上标记任务及t需要的祖先，累计保留子树边权W。s→t路径必在子树内，长度D。
2. 除s→t主链外，每个枝杈需要进入后返回，至少两次；主链边至少一次。因此下界2W−D。沿主链推进并先完成支树DFS可以达到该下界，构成可行性证明。
3. 空task时只剩s→t路径，公式等D；s=t时全部保留边双走。只将task节点直接连线或只取原全树权重会分别漏道路/多走无关枝。

手动走一遍

s与t主链长度5，旁支任务来回长4，总5+4=9，W7、2W−D=9。tasks包含s或t不加额外距离；重复task不改变目标。

Python 参考实现

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

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

from collections import deque

def minimum_walk(count,edges,start,end,tasks):
    if count<=0 or not (0<=start<count and 0<=end<count) or any(not 0<=x<count for x in tasks):raise ValueError("nodes")
    graph=[[] for _ in range(count)]
    if len(edges)!=count-1 or any(w<0 for u,v,w in edges):raise ValueError("nonnegative weighted tree")
    for u,v,w in edges:graph[u].append((v,w));graph[v].append((u,w))
    parent=[None]*count;distance=[0]*count;parent[start]=start;order=[start]
    for u in order:
        for v,w in graph[u]:
            if parent[v] is None:parent[v]=u;distance[v]=distance[u]+w;order.append(v)
    if len(order)!=count:raise ValueError("not connected tree")
    required=set(tasks)|{start,end};keep=[i in required for i in range(count)];weight=0
    for u in reversed(order[1:]):
        if keep[u]:weight+=distance[u]-distance[parent[u]];keep[parent[u]]=True
    return 2*weight-distance[end]

复杂度

O(n)时间/O(n)graph,parent,order,keep；若要输出具体走法，时间还需加输出步数。

易错点与追问

容易失分的边界

• 减的是s→t距离不是树直径。
• 负边加允许重复会导致无界，非负前提不能省。

继续深挖

• 起终点可自由选择时为什么会出现子树直径？
• 带方向道路或一般图时哪部分唯一道路证明失效？