【AtCoder】競プロ典型90問 003 - Longest Circular Road（★4）

2025-11-5

AtCoder/競プロ典型90問/レベル4 AtCoder/緑Diff AtCoder/NoviSteps/1Q AtCoder/グラフ問題/木/木の直径 AtCoder/DFS AtCoder/BFS 競技プログラミング

003 - Longest Circular Road（★4）

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1199 / NoviSteps: 1Q / 配点: 4 点

問題概要

$N$ 個の都市があり、それぞれの都市に $1$ から $N$ までの番号が付けられている。また、 $N-1$ 本の道路があり、 $i$ 本目の道路は都市 $A_i$ と都市 $B_i$ を双方向に結んでいる。

あなたは整数 $u$ , $v$ $(1 \leq u \lt v \leq N)$ を自由に選び、都市 $u$ と都市 $v$ を双方向に結ぶ道路を $1$ 本だけ新設することができる。そこで、以下で定められる値を「スコア」とする。

同じ道を $2$ 度通らずにある都市から同じ都市に戻ってくる経路における、通った道の本数(この値はただ $1$ つに定まる)

このとき、スコアとして考えられる最大の値を出力せよ。

制約

$3 \leq N \leq 100000$
$1 \leq A_i \lt B_i \leq N$ $(1 \leq i \leq N-1)$
どの都市の間も、いくつかの道路を通って移動可能
与えられる入力は全て整数

考察

まず、与えられた都市と道路は、 $N$ 頂点 $N-1$ 辺の木構造で表せるということに気づこう。

木上の任意の 2 頂点を新たな辺で接続すると、その 2 頂点と辺を含む唯一の閉路が生成される。この閉路の長さが本問におけるスコアとなる。

これを最大化するためには、閉路生成前の木において最も離れた 2 頂点を選択すればよい。このような 2 頂点は、木の直径を構成する 2 頂点である。

木の直径を求めるアルゴリズムとして、以下のように 2 回の DFS / BFS を行う方法がある。

適当な頂点 $s$ から DFS / BFS を行い、最も遠い頂点 $u$ を求める。
頂点 $u$ から DFS / BFS を行い、最も遠い頂点 $w$ を求める。このとき、 $u$ と $w$ の距離が木の直径となる。

アルゴリズムの正当性や詳しい解説は以下の記事等を参照のこと。

木の直径を求めるアルゴリズム | アルゴリズムロジック

木に存在する2つノード間の最大距離を木の直径と言います。重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。重み無しの木の例：以下は直径が5となる木の...

アルゴリズムロジック

実装例

ここでは、BFS を用いた実装例を示す。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.template <class T>
7.using Graph = vector<vector<T>>;
8. 
9.template <typename T>
10.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
11. 
12.// ======================================== //
13. 
14.int main()
15.{
16.    int N;
17.    cin >> N;
18.    Graph<int> G(N);
19.    rep(i, 0, N - 1)
20.    {
21.        int A, B;
22.        cin >> A >> B;
23.        A--, B--;
24.        G[A].push_back(B);
25.        G[B].push_back(A);
26.    }
27. 
28.    auto get_dist = [&](int start) -> vector<int>
29.    {
30.        vector<int> res(N, -1);
31. 
32.        auto bfs = [&](int start) -> void
33.        {
34.            queue<int> que;
35.            que.push(start);
36.            res[start] = 0;
37.            while (!que.empty())
38.            {
39.                int now = que.front();
40.                que.pop();
41. 
42.                for (auto next : G[now])
43.                {
44.                    if (res[next] != -1)
45.                        continue;
46. 
47.                    res[next] = res[now] + 1;
48.                    que.push(next);
49.                }
50.            }
51.            return;
52.        };
53. 
54.        bfs(start);
55.        return res;
56.    };
57. 
58.    auto get_farthest = [&](const vector<int> &dist) -> int
59.    {
60.        int res = -1;
61.        int max_dist = -1;
62.        rep(i, 0, N)
63.        {
64.            if (chmax(max_dist, dist[i]))
65.            {
66.                res = i;
67.            }
68.        }
69. 
70.        return res;
71.    };
72. 
73.    vector<int> dist_0 = get_dist(0);
74.    int u = get_farthest(dist_0);
75. 
76.    vector<int> dist_u = get_dist(u);
77.    int v = get_farthest(dist_u);
78. 
79.    cout << dist_u[v] + 1 << endl;
80. 
81.    return 0;
82.}