AtCoder が提供しているABC（AtCoder Beginner Contest）368 D問題をC++とPythonで解いてみました。ABC368は、2024年8月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Minimum Steiner Tree（Difficulty : 816）
問題の詳細は、リンク先をご覧ください。
ABC368 D問題 Minimum Steiner Tree
DFSで、それぞれの枝に含まれる条件を満たす頂点の個数を求めます。AtCoder Problems による Difficulty は 816 でした。
解答案
DFS（深さ優先探索：Depth-First Search）で条件を満たす頂点の数を求めます。
- 探索している頂点自体が指定された頂点に含まれる場合は、戻り値を1増やす（自分自身の分）。
- 自分自身が指定された頂点に含まれていない場合でも、戻り値が1以上である枝があれば、戻り値を1増やす。
C++ プログラム例（ABC368D）
指定された頂点を set コンテナ vk に格納しておきます。
上の考察に従い再帰関数 dfs をコーディングします。グラフは木であるため、親に戻らないようにします。木を DFS する場合の定番コードの背景色を変更しておきます。
関数 dfs を呼び出す場合の頂点は、どの頂点でも構いません。一番値が小さい頂点を指定しました（43行目）。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
set<int> vk;
int dfs(int v, int par)
{
int result = 0;
if (vk.find(v) != vk.end()) {
++result;
}
for (auto next_v : G[v]) {
if (next_v != par) {
int t = dfs(next_v, v);
if ((t > 0)&&(result == 0)) {
++result;
}
result += t;
}
}
return result;
}
int main()
{
int n, k;
cin >> n >> k;
G.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 0; i < k; ++i) {
int t;
cin >> t;
vk.insert(t);
}
cout << dfs(*(vk.begin()), 0) << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC368D）
Python版も基本的な考え方は同じです。再帰関数の呼び出し回数の上限を増やしています（2、4行目）。以下がプログラムです。
"""AtCoder Beginner Contest 368 D"""
import sys
sys.setrecursionlimit(10**6)
def dfs(v, par):
global G, vk
result = 0
if v in vk:
result += 1
for next_v in G[v]:
if next_v != par:
t = dfs(next_v, v)
if t > 0 and result == 0:
result += 1
result += t
return result
n, k = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(n - 1):
a, b = map(int, input().split())
G[a].append(b)
G[b].append(a)
vt = list(map(int, input().split()))
vk = set()
for i in range(k):
vk.add(vt[i])
print(dfs(vt[0], 0))こちらも「AC」と判定されました。
最後に
いくつかの解き方がある問題のようです。グラフの問題を再帰で解くことは、自分にとってなじみがあると考えています。
引き続き ABC の問題を紹介していきます。
