AtCoder が提供しているABC（AtCoder Beginner Contest）361 E問題をC++とPythonで解いてみました。ABC361は、2024年7月6日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Tree and Hamilton Path 2（Difficulty : 1213）
問題の詳細は、リンク先をご覧ください。
ABC361 E問題 Tree and Hamilton Path 2
1周する移動距離から木の直径を引きます。AtCoder Problems による Difficulty は 1213 でした。
解答案
もし、1周するのであれば、すべての頂点を往復する移動の最小距離は、$2 \times \sum C_i$ となります。どの頂点から始めても同じです。
今回の問題は、1周する必要がないため、木の直径（最も遠い頂点間の距離）を $2 \times \sum C_i$ から引けば、求める解となります。直感的に分からなくもないです。厳密な証明は、公式解説をご覧ください。
C++ プログラム例（ABC361E）
前日の記事で、木の直径について解説しました。DFSでもBFSでも解けますが、この記事では、BFSを使ったプログラムを紹介します。移動距離の和の2倍から直径を引いている以外は、前日の記事のプログラムと同じです。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
struct Edge {
int to;
ll weight;
Edge() { }
Edge(int t, ll w) : to(t), weight(w) { }
};
int main()
{
int n;
cin >> n;
ll result = 0;
vector<vector<Edge>> G(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
ll c;
cin >> a >> b >> c;
--a;
--b;
G[a].push_back(Edge(b, c));
G[b].push_back(Edge(a, c));
result += 2 * c;
}
vector<ll> dist(n, -1);
queue<int> que;
que.push(0);
dist[0] = 0;
int max_v = 0;
ll max_dist = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v.to] == -1) {
que.push(next_v.to);
dist[next_v.to] = dist[now] + next_v.weight;
if (dist[next_v.to] > max_dist) {
max_v = next_v.to;
max_dist = dist[next_v.to];
}
}
}
}
dist.assign(n, -1);
que.push(max_v);
dist[max_v] = 0;
max_dist = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v.to] == -1) {
que.push(next_v.to);
dist[next_v.to] = dist[now] + next_v.weight;
max_dist = max(max_dist, dist[next_v.to]);
}
}
}
result -= max_dist;
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC361E）
Python版も基本的な考え方は同じです。キューは deque を使いました。
"""AtCoder Beginner Contest 361 E"""
from collections import deque
n = int(input())
result = 0
G = [[] for _ in range(n)]
for i in range(n - 1):
a, b, c = map(int, input().split())
a -= 1
b -= 1
G[a].append((b, c))
G[b].append((a, c))
result += 2 * c
dist = [-1] * n
que = deque()
que.append(0)
dist[0] = 0
max_v = 0
max_dist = 0
while que:
now = que.popleft()
for next_v in G[now]:
if dist[next_v[0]] == -1:
que.append(next_v[0])
dist[next_v[0]] = dist[now] + next_v[1]
if dist[next_v[0]] > max_dist:
max_v = next_v[0]
max_dist = dist[next_v[0]]
dist = [-1] * n
que.append(max_v)
dist[max_v] = 0
while que:
now = que.popleft()
for next_v in G[now]:
if dist[next_v[0]] == -1:
que.append(next_v[0])
dist[next_v[0]] = dist[now] + next_v[1]
result -= max(dist)
print(result)どちらも「AC」と判定されました。
最後に
この機会に木の直径について学べました。
引き続き ABC の問題を紹介していきます。
