重心分解!
問題概要 (インタラクティブ)
頂点の木が与えられる。なお、この木はどの頂点の次数も 以下であることが保証されている。
A さんは、この木のいずれかの頂点 を考えている。その頂点 を当てるゲームを行う。
あなたは最大 14 回の質問ができる。各質問では 2 つの頂点 を問いかける。A さんは、その 2 つの頂点 のうち、頂点 からの距離がより近い方の頂点を答える。ただし同距離の場合は 0 と答える。
頂点 を当ててください。
制約
考えたこと
できれば 1 回の質問で木のサイズが半分程度になると嬉しい。そこで木の重心分解を使う。
重心を とする。各頂点の次数は最大 5 なので、頂点 に接続している部分木も高々 5 個である。
そのうちの 2 つの部分木の根を質問することにする。このとき
- もし片方の根の方が近ければ、その根を部分木上に答えがある
- もし距離が等しければ、その 2 つの部分木には答えがないので、グラフから除去する (フラグで管理する)
というようにすればよい。このとき、1 回の質問で頂点数が半減するか、2 回の質問で頂点数が 1/4 以下になるので、14 回あれば答えを特定できる。
コード
#include <bits/stdc++.h> using namespace std; // sizeSubtree[v] := v を根とする部分ツリーのサイズ (分割統治の毎ステップごとに再利用) // isRemoved[v] := v が既に取り除かれたかどうか // whoIsParent[v] := ツリーDP時に v の親が誰だったか using Graph = vector<vector<int>>; struct TreeCenteroid { // input Graph tree; // results vector<int> centroids; // intermediate results vector<int> sizeSubtree, isRemoved, whoIsParent; // constructor TreeCenteroid() { } TreeCenteroid(const Graph &tree_) { init(tree_); } // init void init(const Graph &tree_) { tree = tree_; centroids.clear(); sizeSubtree.resize((int)tree.size()); whoIsParent.resize((int)tree.size()); isRemoved.assign((int)tree.size(), false); for (int i = 0; i < (int)tree.size(); ++i) isRemoved[i] = false; } // subroutine void sub_find_centroid(int v, int size, int p = -1) { sizeSubtree[v] = 1; whoIsParent[v] = p; bool isCentroid = true; for (auto ch : tree[v]) { if (ch == p) continue; if (isRemoved[ch]) continue; sub_find_centroid(ch, size, v); if (sizeSubtree[ch] > size / 2) isCentroid = false; sizeSubtree[v] += sizeSubtree[ch]; } if (size - sizeSubtree[v] > size / 2) isCentroid = false; if (isCentroid) centroids.push_back(v); } // first: centroid, second: vectors of (adj-node, size of adj-tree) pair<int, vector<pair<int,int>>> find_centroid(int root, int size) { vector<pair<int, int>> subtrees; centroids.clear(); sub_find_centroid(root, size); int center = centroids[0]; for (auto ch : tree[center]) { if (isRemoved[ch]) continue; if (ch == whoIsParent[center]) { subtrees.push_back(make_pair(ch, size - sizeSubtree[center])); } else { subtrees.push_back(make_pair(ch, sizeSubtree[ch])); } } return make_pair(center, subtrees); } }; bool cmp(pair<int,int> a, pair<int,int> b) { swap(a.first, a.second); swap(b.first, b.second); return a > b; } void dwacon2018_prelims_E() { // 入力 int N, Q; cin >> N >> Q; Graph tree(N); for (int i = 0; i < N - 1; ++i) { int a, b; cin >> a >> b; --a, --b; tree[a].push_back(b); tree[b].push_back(a); } // 重心分解しながらクエリ処理 int curnode = 0, cursize = N, res; TreeCenteroid tc(tree); while (Q--) { pair<int, vector<pair<int, int>>> c = tc.find_centroid(curnode, cursize); int g = c.first; vector<pair<int,int>> chs = c.second; sort(chs.begin(), chs.end(), cmp); if (chs.size() == 1) { cout << "? " << g + 1 << " " << chs[0].first + 1 << endl; int ans; cin >> ans; res = ans; break; } else { cout << "? " << chs[0].first + 1 << " " << chs[1].first + 1 << endl; int ans; cin >> ans; if (ans == chs[0].first + 1) { tc.isRemoved[g] = true; curnode = chs[0].first; cursize = chs[0].second; } else if (ans == chs[1].first + 1) { tc.isRemoved[g] = true; curnode = chs[1].first; cursize = chs[1].second; } else { tc.isRemoved[chs[0].first] = true; tc.isRemoved[chs[1].first] = true; curnode = g; cursize = cursize - chs[0].second - chs[1].second; } if (cursize == 1) { res = curnode + 1; break; } } } cout << "! " << res << endl; } int main() { dwacon2018_prelims_E(); }