けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #615 (Div. 3) F. Three Paths on a Tree

面白かった!!!
ツリーネタでまだこういうのが残ってるんだね!!!

問題へのリンク

問題概要

 N 頂点の木が与えられる。
いま、木の頂点を 3 つ選ぶ (a, b, c とする)。このとき、

  • a と b を結ぶパスに含まれている辺集合
  • b と c を結ぶパスに含まれている辺集合
  • c と a を結ぶパスに含まれている辺集合

の和集合のサイズとして考えられる最大値を求めよ。また、それを実現する具体的な 3 頂点も出力せよ。

制約

  •  3 \le N \le 2 \times 10^{5}

考えたこと

もし 3 つ選ぶのではなく 2 つだったら直径を求める問題ということになる。3 つであっても

  • 直径を求める
  • 直径から最も距離の離れた頂点を求める

とすればよいのでは...という直感がはたらく。反例はなさそうだけど一応簡単に証明してみる。

まず、ある 1 点 v が存在して、求める辺集合は

  • v-a パス
  • v-b パス
  • v-c パス

という風に分解できることに着目する。そうすると実はこの問題は


木の 1 頂点 v を決めうちしたときには、v から各点への距離のベスト 3 を a, b, c とすればよい

v を全頂点について試せばよい


ということがわかる。そう考えると全方位木 DP で解くこともできる。

ここでは直径を利用する方向へと考察を進めてみた。まず直径 p-q を 1 つとってみる。このとき、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがいえれば OK。以下の議論はだいぶごちゃごちゃしてしまっているけど、もう少しスマートにできるのかもしれない。

もし p-q が、v-a, v-b, v-c のいずれとも接点を持たない場合には、v からパス p-q へと向かって行ってたどり着く p-q 上の点を w とする。このとき、v-a 間と、v-b 間を削り取ってしまって、代わりに w をハブ点としてw-p 間、w-q 間、w-c 間を考えてみると、直径の定義から、元のサイズより悪化することはない。

次に、p-q が v-a, v-b, v-c のいずれかと交点をもつときを考える。p から q へと向かうときに最初に交わる点 w が v-a 上の点と仮定して一般性を失わない。このとき直径の定義から、w-q 間が w-a 間より短いことはありえないので、w-q を w-a に組み替えてしまっても良い。この時点で v-p, v-b, v-c の状態になっている。

次に q から p へと向かうときに最初に交わる点 x がどこにあるかで場合分けする

  • v-p 間の点 x で分岐するとき、v-c をなくして x-q を付け加えることで解が悪化することはない (ハブ点が v から x へと入れ替わる)

  • v-b 間の点 x で分岐するとき、x-b をなくして x-q を付け加えることで解が悪化することはない

  • v-c 間の点 x で分岐するとき、x-c をなくして x-q を付け加えることで解が悪化することはない

入り組んでしまったが、いかなる「ハブ点 v と、そこからの距離ベスト 3 の点 a, b, c」の組合せに対しても、解を悪化させることなく「直径 p-q を含む解」に変形できることがわかった。

以上をまとめると、以下のようにして解くことができる。


  • 直径を求める
  • 直径からの距離が最大の点を求める

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

using Graph = vector<vector<int>>;
int N;
Graph G;
 
struct Diameter {
    vector<int> prev;
    pair<int,int> DiameterDFS(const Graph &G, int v, int p) {
        pair<int,int> res(v, 0);
        for (int i = 0; i < (int)G[v].size(); ++i) {
            if (G[v][i] == p) continue;
            pair<int,int> tmp = DiameterDFS(G, G[v][i], v);
            tmp.second++;
            if (tmp.second > res.second) res = tmp, prev[G[v][i]] = v;
        }
        return res;
    }
 
    vector<int> solve(const vector<vector<int> > &G) {
        prev.assign((int)G.size(), -1);
        pair<int,int> leaf = DiameterDFS(G, 0, -1);
        prev.assign((int)G.size(), -1);
        pair<int,int> t = DiameterDFS(G, leaf.first, -1);
        vector<int> res;
        int cur = t.first;
        while (cur != -1) res.push_back(cur), cur = prev[cur];
        return res;
    }
};
 
vector<int> depth;
void rec(int v, int p) {
    depth[v] = depth[p] + 1;
    for (auto ch : G[v]) {
        if (ch == p) continue;
        rec(ch, v);
    }
}
 
void solve() {
    Diameter Dia;
    auto di = Dia.solve(G);

    // 直径から各頂点への距離を求める
    depth.assign(N, 0);
    for (int i = 1; i+1 < di.size(); ++i) {
        int v = di[i];
        for (auto to : G[v]) {
            if (to == di[i-1] || to == di[i+1]) continue;
            rec(to, v);
        }
    }
    int a = di[0], b = di.back(), c = -1;
    int ma = 0;
    for (int v = 0; v < N; ++v) if (chmax(ma, depth[v])) c = v;
    if (c == -1) for (int v = 0; v < N; ++v) if (v != a && v != b) c = v;
 
    printf("%d\n", ma + (int)di.size() - 1);
    printf("%d %d %d\n", a+1, b+1, c+1);
}
 
int main() {
    scanf("%d", &N);
    G.assign(N, vector<int>());
    for (int i = 0; i < N-1; ++i) {
        int u, v; scanf("%d %d", &u, &v); --u, --v;
        G[u].push_back(v); G[v].push_back(u);
    }
    solve();
}