题目内容
输入输出描述
样例
输入
4 2
2 1 1
1 3 2
4 3 2
3 2
4 2
输出
10
题目解析
代码实现
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);
}
}