【AtCoder】ABC 428 E - Farthest Vertex

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1167 / NoviSteps: 1D / 配点: 475 点

問題概要

頂点に 11 から NN の番号がついた NN 頂点の木があり、 ii 番目の辺は頂点 AiA_i と頂点 BiB_i を結ぶ辺である。

頂点 uu と頂点 vv の距離を、頂点 uu と頂点 vv を両端点とするパスに含まれる辺の本数として一意に定義する。

v=1,2,…,Nv = 1, 2, \dots, N について次の問題を解け。

  • 頂点 1,2,…,N1, 2, \dots, N のうち頂点 vv からの距離が最大となる頂点の番号を出力せよ。 ただし、条件を満たす頂点が複数存在する場合は最も番号が大きい頂点を出力すること。

制約

  • 2≤N≤5×1052 \leq N \leq 5 \times 10^5
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • 入力される値は全て整数

考察

木上の 2 頂点間の最大距離は、「木の直径」と呼ばれている。

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

  1. 適当な頂点 ss から DFS / BFS を行い、最も遠い頂点 uu を求める。
  2. 頂点 uu から DFS / BFS を行い、最も遠い頂点 ww を求める。このとき、 uu と ww の距離が木の直径となる。

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

木の直径を求めるアルゴリズム | アルゴリズムロジック
木の直径を求めるアルゴリズム | アルゴリズムロジック
木に存在する2つノード間の最大距離を木の直径と言います。 重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。 重み無しの木の例： 以下は直径が5となる木の...
アルゴリズムロジック
algo-logic.info favicon

さて、本問題では各頂点 vv について、頂点 vv からの距離が最大となる頂点を求める必要があるが、面倒なのは、そのような頂点が複数存在する場合は最も番号が大きい頂点を出力することである。

したがって、上記のアルゴリズムで求めた木の直径の両端点 u,wu, w について、各頂点 vv が uu と ww のどちらから遠いかを判定するために、uu から各頂点への距離、ww から各頂点への距離をそれぞれ求めておく。

前者は木の直径を求める過程で得られるが、後者は頂点 ww から改めて DFS / BFS を行うことで求めることができる。

abc428e_fig_1.webp

上図で例えると、

  1. 1 回目の探索で頂点 11 から探索を行い、最も遠い頂点 uu を求める。
  2. 2 回目の探索で頂点 uu から探索を行い、最も遠い頂点 ww を求める。この過程で、 uu を始点とした各頂点への距離(オレンジの数字)が求まる。
  3. 3 回目の探索で頂点 ww から探索を行い、各頂点への距離(緑の数字)を求める。

となる。最終的に、

  • v=av = a のとき、頂点 aa は uu からの距離が 44、ww からの距離が 66 なので、答えは ww である。
  • v=bv = b のとき、頂点 bb は u,wu, w からの距離が共に 55 なので、答えは max⁡(u,w)\max(u, w) である。

と答えを求めることができる。


全体の計算量は、DFS / BFS を 33 回行うので O(N)O(N) である。

実装例

今回は DFS で実装した。 こういうときはラムダ式で書くとmain関数内で書き下せるので便利である。

また、実装例では頂点を 0-indexed としているので、答えに +1+1 して出力することに注意。

CPP
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 dfs = [&](auto &self, int now, int parent, int d) -> void
33.        {
34.            res[now] = d;
35.            for (auto next : G[now])
36.            {
37.                if (next == parent)
38.                    continue;
39. 
40.                self(self, next, now, d + 1);
41.            }
42.            return;
43.        };
44. 
45.        dfs(dfs, start, -1, 0);
46.        return res;
47.    };
48. 
49.    auto get_farthest = [&](const vector<int> &dist) -> int
50.    {
51.        int res = -1;
52.        int max_dist = -1;
53.        rep(i, 0, N)
54.        {
55.            if (dist[i] > max_dist)
56.            {
57.                res = i;
58.                max_dist = dist[i];
59.            }
60.            else if (dist[i] == max_dist)
61.            {
62.                chmax(res, i);
63.            }
64.        }
65. 
66.        return res;
67.    };
68. 
69.    vector<int> dist_0 = get_dist(0);
70.    int u = get_farthest(dist_0);
71. 
72.    vector<int> dist_u = get_dist(u);
73.    int w = get_farthest(dist_u);
74. 
75.    vector<int> dist_w = get_dist(w);
76. 
77.    rep(v, 0, N)
78.    {
79.        int from_u = dist_u[v];
80.        int from_w = dist_w[v];
81. 
82.        if (from_u == from_w)
83.        {
84.            cout << max(u, w) + 1 << endl;
85.        }
86.        else if (from_u < from_w)
87.        {
88.            cout << w + 1 << endl;
89.        }
90.        else
91.        {
92.            cout << u + 1 << endl;
93.        }
94.    }
95. 
96.    return 0;
97.}
Submission #70261263 - AtCoder Beginner Contest 428
Submission #70261263 - AtCoder Beginner Contest 428
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
atcoder.jp favicon

実装時間: 60 分

コメント

「最も番号が大きい頂点を出力する」というひねりが良い味を出していると思った。

関連記事