题解

题目描述

物流公司总部位于编号为 $1$ 的地点，城市共有 $N$ 个地点、$N-1$ 条连通所有地点的公路。今天有 $M$ 条寄送任务，每条任务都由一个寄件地 $s$ 和一个收件地 $t$（均在 $2\le s,t\le N$，且 $s\neq t$）组成。

运输车工作流程分两阶段：

1. 收件阶段：从总部（$1$）出发，按任意顺序跑到所有寄件地点 $\{s_i\}$，收取货物后回到总部（$1$）扫描。
2. 送件阶段：从总部（$1$）出发，按任意顺序将扫描后的货物送到所有送件地点 $\{t_i\}$，送完后回总部（$1$）。

要求：求完成所有任务时运输车最少行驶的总里程。任务的先后顺序可任意安排。

问题本质分析

• 两阶段可以独立看待：收件阶段和送件阶段。
• 每个阶段都类似「从根节点出发，遍历一组目标节点后回到根」的树上最短遍历路程问题。
• 在树上，若要从根 $1$ 出发，访问目标集合 $X$ 中所有节点，最后回到根，最优花费等于： 即把目标节点到根路径上的所有边去重后各自走两遍。

因此，令

• $S=\{s_1,\dots,s_M\}$ 为所有寄件地点，
• $T=\{t_1,\dots,t_M\}$ 为所有送件地点，

分别在以 $1$ 为根的树上，统计每条边在 $S$ 子树中出现的情况与在 $T$ 子树中出现的情况，累加其权重，各自乘 $2$，再相加即可。

思路

1. 建图，选定 $1$ 为根，对树做一次 DFS（或 BFS）得到父节点数组和树的拓扑顺序。
2. 准备两个计数数组：cntS[u] 表示以 $u$ 为根的子树内寄件点数量；同理 cntT[u]。
3. 对每个任务 $(s_i,t_i)$，令 cntS[s_i]++，cntT[t_i]++。
4. 按 后序（从叶到根）遍历节点，将子树的计数汇总到父节点：

   for u in 拓扑倒序:
     cntS[parent[u]] += cntS[u]
     cntT[parent[u]] += cntT[u]
   

5. 再次遍历所有非根节点 $u$，若 cntS[u]>0，则收件阶段需走过边 $(u, parent[u])$；同理若 cntT[u]>0，送件阶段需走过该边。累加相应阶段的边权重。
6. 结果 = $2\times$(收件阶段累加) + $2\times$(送件阶段累加)。

C++

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int MAXN = 100000 + 5;

int N, M;
vector<pair<int,int>> adj[MAXN]; // 邻接表： (邻居, 权重)
int fa[MAXN];                    // 父节点
int order[MAXN], ord_cnt;        // BFS/DFS 拓扑序
ll cntS[MAXN], cntT[MAXN];       // 子树内寄件计数、送件计数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        adj[i].clear();
        cntS[i] = cntT[i] = 0;
    }

    // 读入 N-1 条边
    for (int i = 0; i < N-1; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    // 以 1 为根，BFS 建立父节点和拓扑序
    queue<int> q;
    vector<bool> vis(N+1, false);
    q.push(1);
    vis[1] = true;
    ord_cnt = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order[ord_cnt++] = u;
        for (auto [v, w] : adj[u]) {
            if (!vis[v]) {
                vis[v] = true;
                fa[v] = u;
                q.push(v);
            }
        }
    }

    // 读任务，标记寄件点和送件点
    for (int i = 0; i < M; i++) {
        int s, t;
        cin >> s >> t;
        cntS[s]++;
        cntT[t]++;
    }

    // 后序汇总子树计数（倒序遍历拓扑序）
    for (int i = ord_cnt - 1; i > 0; i--) {
        int u = order[i];
        cntS[fa[u]] += cntS[u];
        cntT[fa[u]] += cntT[u];
    }

    // 累加答案
    ll sumS = 0, sumT = 0;
    for (int u = 2; u <= N; u++) {
        int p = fa[u];
        // 找到父子边权
        int w = 0;
        for (auto [v, wt] : adj[u]) {
            if (v == p) { w = wt; break; }
        }
        if (cntS[u] > 0) sumS += w;
        if (cntT[u] > 0) sumT += w;
    }

    // 总路程
    ll ans = 2 * (sumS + sumT);
    cout << ans << "\n";
    return 0;
}

Python

from collections import deque
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, c = map(int, input().split())
        adj[u].append((v, c))
        adj[v].append((u, c))

    # BFS 建立父节点与拓扑序
    fa = [0] * (N+1)
    order = []
    q = deque([1])
    visited = [False] * (N+1)
    visited[1] = True
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in adj[u]:
            if not visited[v]:
                visited[v] = True
                fa[v] = u
                q.append(v)

    # 子树计数
    cntS = [0] * (N+1)
    cntT = [0] * (N+1)
    for _ in range(M):
        s, t = map(int, input().split())
        cntS[s] += 1
        cntT[t] += 1

    # 后序汇总
    for u in reversed(order[1:]):  # 跳过根 1
        cntS[fa[u]] += cntS[u]
        cntT[fa[u]] += cntT[u]

    sumS = sumT = 0
    # 累加各边权
    for u in range(2, N+1):
        p = fa[u]
        # 找到边权
        for v, w in adj[u]:
            if v == p:
                if cntS[u] > 0:
                    sumS += w
                if cntT[u] > 0:
                    sumT += w
                break

    ans = 2 * (sumS + sumT)
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static List<int[]>[] adj;
    static int[] fa, order;
    static long[] cntS, cntT;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new List[N+1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

        // 读边
        for (int i = 0; i < N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            adj[u].add(new int[]{v, c});
            adj[v].add(new int[]{u, c});
        }

        // BFS 建树
        fa = new int[N+1];
        order = new int[N];
        boolean[] vis = new boolean[N+1];
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);
        vis[1] = true;
        int idx = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            order[idx++] = u;
            for (int[] e : adj[u]) {
                int v = e[0];
                if (!vis[v]) {
                    vis[v] = true;
                    fa[v] = u;
                    q.offer(v);
                }
            }
        }

        cntS = new long[N+1];
        cntT = new long[N+1];
        // 读任务
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            cntS[s]++;
            cntT[t]++;
        }

        // 后序汇总
        for (int i = N-1; i > 0; i--) {
            int u = order[i];
            cntS[fa[u]] += cntS[u];
            cntT[fa[u]] += cntT[u];
        }

        long sumS = 0, sumT = 0;
        // 累加边权
        for (int u = 2; u <= N; u++) {
            int p = fa[u];
            int w = 0;
            for (int[] e : adj[u]) {
                if (e[0] == p) {
                    w = e[1];
                    break;
                }
            }
            if (cntS[u] > 0) sumS += w;
            if (cntT[u] > 0) sumT += w;
        }

        long ans = 2 * (sumS + sumT);
        System.out.println(ans);
    }
}

题目内容

物流公司每天都要处理很多物流的运输工作，整个城市共有$N$个地点。共有$N-1$条公路，每$2$个地点之间都能通过公路连通。物流公司总部位于$1$号地点。

今天有一辆物流运偷车共有$M$条物流运输任务，物流运输车每天的工作 流程如下:

先要从总部出发去收取所有的寄件货物，收到所有货物后回到总部扫描货物，再从总部出发将货物送至所有的送件地址，送完后最终回到总部，算作完成了今天的运输工作。

请问该辆物流运输车今天最少行驶多少路程可以完成今天的运输工作，运输任务不分先后。

输入描述

对于每组数据，第一行有$2$个整数，依次为 $N(3 ≤N≤ 10^5),M(1≤M≤10^5)$，表示有$N$个地点和 $M$条物流任务，数字用空格分开。

接下来有$N-1$行，每行有$3$个整数，依次为

$u(1≤u≤N),v(1≤v≤N),(1≤c≤10^5)$,表示从$u$到$v$有一条公路，

公路里程为$c$，输入保证所有地点连通。

接下来有$M$ 行，每行有$2$个整数，依次为$s(2 ≤s ≤ N),t(2 ≤t≤ N,s≠t)$

表示寄件任务从$s$寄到$t$

输出描述

输出一个整数，表示该辆物流运输车最少行驶多少路程能够完成今天的运输工作。

样例1

输入

4 2 
2 1 1
1 3 2
4 3 2
3 2 
4 2

输出

10

说明

运输车从地点$1$开到地点$3$接收任务$1$物品，再开到地点$4$接收任务$2$物品，回到总部$1$扫描，扫描后将任务$1$和任务$2$的物品送到地点$2$，最终回到总部$1$，总共行驶里程$10$。

样例2

输入

5 2
2 1 1
1 3 2
4 3 2
1 5 3
4 2
5 4

输出

24

说明

运输车从地点$1$开到地点$5$接收任务$2$物品，再开到地点$4$接收任务$1$物品，回到总部$1$扫描，扫描后将开到地点$4$完成任务$2$，再开到地点$2$完成任务$1$，最终回到总部$1$，总共行驶里程$24$