天下一プログラマーコンテスト2015本戦 F - 根付き木のみさわさん
解法
まずオイラーツアーしてそれぞれの頂点が最初に現れる場所(下のソースコードで言うと BEGIN)を覚えておきます。
すると, クエリで与えられる M 個の頂点の中で K 個の頂点を囲う区間というのは, オイラーツアーで並べられた頂点の中から K 個の連続した区間を取ったものになります。つまり, K 個の頂点のうち左端と右端の LCA を取ればそれが K 個の頂点を囲っていることになります。
よって, 各クエリでやるべきことは,
・頂点をオイラーツアー順にソート
・オイラーツアー順で i 番目と i+K-1 番目の頂点の LCA を取り, depth が最大のものを求める
得た知見
- オイラーツアーの列からはかなりいろんな情報が得られる
- 今回は特に「区間 <-> 部分木」という基本的な情報を少し応用した
class Tree { public: Tree(int V, int root) : V(V), root(root) { T.resize(V); for (int i = 0; i < MAXLOGV; i++) parent[i].resize(V); depth.resize(V); } // uとvをつなぐ // lcaを求めることが主目的なので無向グラフとしている void unite(int u, int v) { T[u].push_back(v); T[v].push_back(u); } // initする // コンストラクタだけじゃなくてこれも呼ばないとlcaが求められないぞ void init() { dfs(root, -1, 0); for (int k = 0; k+1 < MAXLOGV; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k+1][v] = -1; else parent[k+1][v] = parent[k][parent[k][v]]; } } } // uとvのlcaを求める int lca(int u, int v) const { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAXLOGV; k++) { if ((depth[v] - depth[u])>>k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAXLOGV-1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } // uとvの距離を求める // edgeを定義しないといけない時はこれじゃダメ int dist(int u, int v) const { int p = lca(u, v); return (depth[u]-depth[p]) + (depth[v]-depth[p]); } void dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int next : T[v]) { if (next != p) dfs(next, v, d+1); } } static const int MAXLOGV = 25; // グラフの隣接リスト表現 vector<vector<int> > T; // 頂点の数 int V; // 根ノードの番号 int root; // 親ノード vector<int> parent[MAXLOGV]; // 根からの深さ vector<int> depth; }; // Euler-Tour const int MAXSIZE = 100020; int BEGIN[MAXSIZE], END[MAXSIZE]; vector<int> euler_tour; int K; vector<vi> G; void createEulerTour(int v, int p) { BEGIN[v] = K++; euler_tour.push_back(v); for (int el : G[v]) { if (el == p) continue; createEulerTour(el, v); euler_tour.push_back(v); K++; } END[v] = K; } bool cmp(int u, int v) { return BEGIN[u] < BEGIN[v]; } int V[MAXSIZE]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; Tree tree(N, 0); for (int i = 0; i < N-1; i++) { int a, b; cin >> a >> b; a--; b--; tree.unite(a, b); } tree.init(); G = tree.T; createEulerTour(0, -1); int Q; cin >> Q; while (Q--) { int m, k; cin >> m >> k; for (int i = 0; i < m; i++) { cin >> V[i]; V[i]--; } sort(V, V+m, cmp); int ans = 0; for (int i = 0; i + k <= m; i++) { int lca = tree.lca(V[i], V[i+k-1]); ans = max(ans, tree.depth[lca]); } cout << ans << endl; } return 0; }