一个都不删的情况：最优肯定是最长链放在最后不回溯

要删点： 注意到如果一个关键节被删，那它上面有一段的路不用走，具体的，就是止步于分支节点或者另一个关键点，而这个分支节点恰好是被删节点和其他关键节点最近公共祖先（下简称父亲）。

所以对关键点新建一棵树 $G$，边权 $val_u$ 就是关键点 u 到父亲的距离。利用递归栈的性质可以实现。

记总长 $sum$ 就是完全走完的路线长度（所有关键点都不删，每走完一个关键点就回到根）。

如果删了一个 $G$ 的叶子 $u$：

那 $u$ 到它父亲这条路不用走了，$sum$ 减去 $val_u$。然后依旧把最长链留到最后不回溯，根据 $sum$ 的定义，$sum$ 把最长链多算了一次，要减去最长链的长度

另外最长链只有两种可能：原树最长链和原树非严格次长链

当然并不需要真的建这颗树，我们需要信息的有且仅有这个节点到父亲的边权是多少，直接维护 $val_i$。

综上所述

答案是 $sum - [u \ 在 \ G \ 中是叶子] * val_u - 当前最长链的长度$

巡检调整：从一条边是否还要走开始

先只求一个方案

把树定根在 1。考虑父亲到儿子 u 的边：如果 u 的子树中还有任务，这条边一定得走；否则没必要走。把所有必须走的边的长度加起来，记为 W。

如果要求最后回到 1，每条必要边至少走两次，按 DFS 的顺序走就能做到，总长度是 2W。

现在不要求回来。假设最后停在任务点 v，那么从 1 到 v 的路径可以只走一次，其他必要边仍然走两次。因此路线长度是

$$2W-\operatorname{dist}(1,v).$$

为什么能做到？经过一条最终要停留的路径时，先走完旁边的支路并返回，再走向路径的下一点。最后恰好停在 v。为什么不能更短？任何不在 1 到终点路径上的必要边，都必须跨过去再跨回来；路径上的必要边也至少走一次。

正边权保证没有必要停在必要子树外。必要子树中最深的点可以取为任务点，所以选择离 1 最远的剩余任务即可。没有剩余任务时，W 和最远距离都按 0 计算。

不要取消一次就重新遍历

一条边原来需要走，取消 x 后不需要走，说明这条边下方原来只有一个任务，而且就是 x。

这给出了直接的统计办法。令 cnt[u] 表示 u 的子树中有多少任务：

• cnt[u]=0：父边原来就不用走。
• cnt[u]=1：父边只为这一个任务服务，把边权记到这个任务名下。
• cnt[u]≥2：取消任意一个任务后，父边都还要走。

记 delta[x] 为只为 x 服务的所有边权之和，那么取消 x 后的必要边权和就是 W-delta[x]。

注意这里可能减少整条支路，不只是 x 的父边；如果 x 下方还有其他任务，也可能一条边都不能减少。

为了知道唯一任务是谁，可以在子树 DP 中维护一个任务编号，也可以维护编号异或和。参考程序用异或和 who[u]；只在 cnt[u]=1 时把它当作任务编号使用，不是用异或值判断任务是否唯一。

最远任务也要跟着更新

所有点到 1 的距离都不会变。预处理任务距离的最大值、次大值以及最大值对应的一个任务。

取消的不是这个任务，就仍取最大值；取消了它，就取次大值。最大值允许并列：有两个任务一样远时，次大值应等于最大值，不能求“严格次大”。只有一个任务时，次大值记为 0。

最终答案为

$$\boxed{2(W-\mathrm{delta}[x])-\max_{y\ne x,\ y\text{ 是任务}}\operatorname{dist}(1,y)}.$$

程序怎么对应

先用 ord 记录从父亲到儿子的遍历顺序，同时求 fa、dis 和父边长度 cost。倒序扫描 ord，累加子树的 cnt、who，统计 W 和 delta。最后扫描任务求距离前两名，逐个输出。

这是两次线性遍历，不需要 LCA、虚树、换根 DP 或优先队列。时间 O(n+k)，空间 O(n)。链的长度可以达到 200000，参考程序不用递归。距离与答案用 long long。

部分分为什么这样设

子任务	分数	能成立的做法及作用
n≤10、k≤8	10	对每个取消方案，在“当前点、已访问任务集合”上跑最短路；可以不先发现树上路线公式。
n≤2000	20	每取消一个任务，就重新统计必要边与最远任务，O(nk)。对应已经解决单次询问，还没解决批量处理。
每条边都连着 1	15	任务各自占一条支路，直接维护任务边权和及前两大值；帮助理解“来回走，最后一段不返回”。
k=n	20	除 n=1 外，取消非根叶子只去掉它的父边，取消其他点不去掉任何边；再处理最远距离。无需任意任务分布下的唯一任务归属。
无限制	35	把每条边归给其下方唯一任务，批量统计取消影响。

这是各子任务对应的思考路线。逐次重算、星形和全任务做法已分别编写并进行本地测分，结果见验收报告；小规模状态搜索也用于独立对拍。

容易错在哪里

• 把取消任务理解为删点，样例 2 已经能区分。
• 只减去任务点的父边，会漏掉整条无人需要的支路。
• 只更新 W，不更新最远任务。样例 2 取消点 3 后答案是 2，不能仍减去旧距离 7。
• 次大值去重，遇到两个同样远的任务会出错。
• 把所有边都计入 W，树上没有任务的旁枝会多算。

独立校验使用“当前位置、已访问任务集合”上的 Dijkstra，不复用上面的边贡献公式。1600 组随机小数据、4920 个答案及三个题面样例通过；20 万点链、星形的全部答案也进行了核对。本次另外生成了正式数据和独立下发样例，并实测常见部分分与错解；目标评测服务器的时限校准尚未进行。

参考程序

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
struct Edge { int v; ll w; };
void solve() {
    int n, k;
    cin >> n >> k;
    vector<vector<Edge>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        e[u].push_back({v, w}); e[v].push_back({u, w});
    }
    vector<int> x(k), cnt(n + 1), who(n + 1), fa(n + 1), ord(1, 1);
    vector<ll> dis(n + 1), cost(n + 1), delta(n + 1);
    for (int &u : x) { cin >> u; cnt[u] = 1; who[u] = u; }
    for (int i = 0; i < n; i++) {
        int u = ord[i];
        for (auto t : e[u]) if (t.v != fa[u]) {
            fa[t.v] = u; cost[t.v] = t.w;
            dis[t.v] = dis[u] + t.w; ord.push_back(t.v);
        }
    }
    ll sum = 0;
    for (int i = n - 1; i > 0; i--) {
        int u = ord[i], p = fa[u];
        if (cnt[u]) sum += cost[u];
        if (cnt[u] == 1) delta[who[u]] += cost[u];
        cnt[p] += cnt[u]; who[p] ^= who[u];
    }
    ll first = -1, second = 0;
    int pos = -1;
    for (int u : x) {
        if (dis[u] > first) { second = max(0LL, first); first = dis[u]; pos = u; }
        else second = max(second, dis[u]);
    }
    for (int u : x) {
        ll far = u == pos ? second : first;
        cout << 2 * (sum - delta[u]) - far << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int t = 1;
#ifdef SELF_TEST_BATCH
    cin >> t;
#endif
    while (t--) solve();
}