天下一プログラマーコンテスト2015本戦 F - 根付き木のみさわさん

,

heavy-light decompositionを使う問題と聞いて解き始めたのだけど、euler tour + lcaが想定解法ぽくて、euler tourも書いたことがなかったのでeuler tourで解いた。 euler tour解を思い付けと言われると厳しいが、解法を聞いて書くだけなら苦労しない。

F - 根付き木のみさわさん

問題

頂点数$N$の根付き木($N \le 10^5$)が与えられる。以下のクエリが$Q$個($Q \le 10^5$)与えられるので処理せよ。

$M$個の頂点が指定される。指定された頂点を子孫(それ自身を含む)に$K$個以上含む頂点で、深さが最も深いものの深さを答えよ。($K \le M \le N$)

解法

euler tour + lowest common ancestor。 指定された頂点をdfsの通りがけ順に、つまりeuler tourしたときのindexの順に整列する。その列の$i$項目と$i+K-1$項目のlcaとして与えられる頂点で、最も深いものの深さが答え。

指定された頂点から$K$個取りだしてそれら全てのlcaでできる頂点で、最も深いものの深さは答えである。 近い頂点からなる組合せだけを見れば十分であることから、euler tourの順に並べて隣接する$K$項だけ見ればよい。 eular tourの順に並べているので、その端と端のlcaを取ればそれが$K$個の頂点全てのlcaと一致する。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
#define repeat(i,n) repeat_from(i,0,n)
#define repeat_from_reverse(i,m,n) for (int i = (n)-1; (i) >= (m); --(i))
#define repeat_reverse(i,n) repeat_from_reverse(i,0,n)
using namespace std;
void count_depths(int v, int p, vector<vector<int> > const & g, int d, vector<int> & depth) {
    depth[v] = d;
    for (int w : g[v]) if (w != p) {
        count_depths(w, v, g, d+1, depth);
    }
}
vector<int> count_depths(int p, vector<vector<int> > const & g) {
    vector<int> depth(g.size());
    count_depths(p, -1, g, 0, depth);
    return depth;
}
void make_ancestors(int v, int p, vector<vector<int> > const & g, vector<int> & anc) {
    anc[v] = p;
    for (int w : g[v]) if (w != p) {
        make_ancestors(w, v, g, anc);
    }
}
vector<int> make_ancestors(int p, vector<vector<int> > const & g) {
    vector<int> anc(g.size());
    make_ancestors(p, -1, g, anc);
    return anc;
}
struct lowest_common_ancestor_t {
    int p;
    vector<vector<int> > a;
    vector<int> depth;
    explicit lowest_common_ancestor_t(int a_p, vector<vector<int> > const & g) {
        p = a_p;
        int n = g.size();
        a.resize(1 + floor(log2(n)));
        int l = a.size();
        a[0] = make_ancestors(p, g);
        repeat_from (k,1,l) {
            a[k].resize(n);
            repeat (j,n) {
                if (a[k-1][j] == -1) {
                    a[k][j] = -1;
                } else {
                    a[k][j] = a[k-1][a[k-1][j]];
                }
            }
        }
        depth = count_depths(p, g);
    }
    int get(int v, int w) {
        int l = a.size();
        if (depth[v] != depth[w]) {
            if (depth[v] < depth[w]) swap(v, w);
            assert (depth[v] > depth[w]);
            repeat_reverse (k,l) {
                if (a[k][v] != -1 and depth[a[k][v]] >= depth[w]) {
                    v = a[k][v];
                }
            }
        }
        assert (depth[v] == depth[w]);
        if (v == w) return v;
        repeat_reverse (k,l) {
            if (a[k][v] != a[k][w]) {
                v = a[k][v];
                w = a[k][w];
            }
        }
        assert (v != w);
        assert (a[0][v] == a[0][w]);
        assert (a[0][v] != -1);
        return a[0][v];
    }
};
void make_euler_tour(int v, int p, vector<vector<int> > const & g, int & i, vector<int> & ix) {
    ix[v] = i ++;
    for (int w : g[v]) if (w != p) {
        make_euler_tour(w, v, g, i, ix);
    }
}
vector<int> make_euler_tour(int p, vector<vector<int> > const & g) {
    int i = 0;
    vector<int> ix(g.size());
    make_euler_tour(p, -1, g, i, ix);
    return ix;
}
int main() {
    int n; cin >> n;
    vector<vector<int> > g(n);
    repeat (i,n-1) {
        int a, b; cin >> a >> b;
        -- a; -- b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> euler = make_euler_tour(0, g);
    vector<int> depth = count_depths(0, g);
    lowest_common_ancestor_t lca(0, g);
    int q; cin >> q;
    repeat (query,q) {
        int m, k; cin >> m >> k;
        vector<int> vs(m);
        for (int & v : vs) {
            cin >> v; -- v;
        }
        sort(vs.begin(), vs.end(), [&](int v, int w) -> bool {
            return euler[v] < euler[w];
        });
        int d = 0;
        for (int i = 0; i+k-1 < m; ++ i) {
            d = max(d, depth[lca.get(vs[i], vs[i+k-1])]);
        }
        cout << d << endl;
    }
    return 0;
}