Codeforces Round #328 (Div. 2) D. Super M

問題

codeforces.com

解法

たとえば次のような木が与えられたとする。

始点を2、終点を7と決めると次のような経路になることが確定する。

この経路をよく見ると、

のようになっている。つまり、

（必要な時間）=（黄色同士を繋ぐ木の辺の数）*2-（2-7パスの長さ）

になっている。一般に始点をs、終点をtとしたとき

（必要な時間）=（黄色同士を繋ぐ木の辺の数）*2-（s-tパスの長さ）

になっている。s-tパスの長さが最大のとき必要な時間が最小になるため、s-tパスの長さを最大化する問題を解けばいいことになる。つまりこの問題は、最小のインデックスの頂点を持った最遠点対を求める問題ということができる。

最遠点対を求めるO(E)のアルゴリズムがあるため、これを使うことを考える。このアルゴリズムでは以下の3つのステップを行う。

1. 適当にu∈Vを持ってくる
2. uから一番遠い点vを求める
3. vから一番遠い点wを求める

ステップ終了時の(v,w)が最遠点対になっている。
今回欲しいのは最小のインデックスの頂点を使った最遠点対だから、先ほどのアルゴリズムを少し書き換えてみる。

1. 適当にu∈Vを持ってくる
2. uから一番遠く、かつインデックス最小の点vを求める
3. vから一番遠く、かつインデックス最小の点wを求める

実はこれで最小のインデックスを持つ最遠点対(v,w)を得ることができる。正当性の証明は別記事の事実を用いる。pekempey.hatenablog.com

証明：最遠点対の候補である最小インデックスの頂点をxとする。uとxが中心を挟んでるかどうかで振るまいが変わる。まずuとxが中心を挟んでいる場合、vがただちにxになる。次にuとxが中心を挟んでいない場合、vは中心を通って反対側の頂点になり、wはxになる。

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

int n, m;
const int inf = 1e9;
vector<int> G[202020];
int color[202020];
int has_black[202020];

void dfs(int curr, int prev = -1) {
    if (color[curr]) has_black[curr] = true;
    for (int next : G[curr]) if (next != prev) {
        dfs(next, curr);
        has_black[curr] |= has_black[next];
    }
}

int dfs2(int curr, int prev = -1) {
    int res = 0;
    for (int next : G[curr]) if (next != prev) {
        if (has_black[next]) {
            res += 1 + dfs2(next, curr);
        }
    }
    return res;
}

pair<int, int> farthest(int u) {
    vector<int> dist(n, inf);
    dist[u] = 0;
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int w : G[v]) {
            if (chmin(dist[w], dist[v] + 1)) {
                q.push(w);
            }
        }
    }
    rep (i, n) if (!color[i]) dist[i] = -inf;
    auto mx = max_element(dist.begin(), dist.end());
    return make_pair(mx - dist.begin(), *mx);
}

int main() {
    cin >> n >> m;
    rep (i, n - 1) {
        int u, v;
        scanf("%d %d", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int u, v, w;
    rep (i, m) {
        int x;
        scanf("%d", &x);
        x--;
        color[x] = true;
        u = x;
    }
    dfs(u);
    int total = dfs2(u);

    v = farthest(u).first;
    int dist;
    tie(w, dist) = farthest(v);

    int ans = min(v, w) + 1;
    cout << ans << endl;
    cout << total * 2 - dist << endl;
    return 0;
}

コメント

teleportation と exactly once を見て一回だけワープできる問題かと思ってしまった。