第4回 ドワンゴからの挑戦状 予選,E: ニワンゴくんの家探し

Tree

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_e

これはそんなに難しくない。

重心分解して、一番部分木が大きい頂点から列挙します。
重心がsだとして、子が{a, b, c, d, e}だったとします。
そしたら(a,b)をまず聞いてaだったらaの木に潜りbだったらbの木に潜ります。0だったら(c,d)を聞きます。
同じようにして(c,d)が0の時は(s,e)を聞いてeならeの木に潜り、sならsを出力します。

こうすれば(a,b)で潜る木が確定すれば1回の質問で元の木の1/2未満に、
(c,d)で潜る木が確定すれば2回の質問で元の木の1/3未満に、
(e,s)で潜る木が確定すれば3回の質問で元の木の1/5未満になります。

効率的に一番劣っているのは(e,s)で潜る木が確定する場合ですが、
5^(12/4)=625なのでN=2000なら12回質問することで候補を3頂点に絞れ、あとの2回で求める頂点を確定できそうだとわかります。

あとendlで出力しないとTLEするので注意しましょう。

namespace CD { //centroid decomposition

	struct edge { int to, length; };

	vector<edge> G[MAX_N];
	bool centroid[MAX_N];
	int subtree_size[MAX_N];

	void init(int n) {
		rep(i, 0, n) G[i].clear();
	}
	void add_edge(int a, int b, int c) {
		G[a].push_back((edge){b, c});
		G[b].push_back((edge){a, c});
	}

	int compute_subtree_size(int v, int p) {
		int c = 1;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			c += compute_subtree_size(G[v][i].to, v);
		}
		subtree_size[v] = c;
		return c;
	}

	pi search_centroid(int v, int p, int t) { 
		pi res = pi(inf, -1);
		int s = 1, m = 0;
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;

			MIN(res, search_centroid(w, v, t));

			MAX(m, subtree_size[w]);
			s += subtree_size[w];
		}
		MAX(m, t - s);
		MIN(res, pi(m, v));
		return res;
	}


	void solve_subproblem(int v) {
		compute_subtree_size(v, -1);
		int cen = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[cen] = true;

		set<pi> s;

		rep(i, 0, (int)G[cen].size()) {
			int n = G[cen][i].to;
			if(centroid[n]) continue;
			s.insert(pi(-subtree_size[n], n));
		}

		while(sz(s) >= 2) {
			auto p1 = (*s.begin()); s.erase(p1);
			auto p2 = (*s.begin()); s.erase(p2);
			int a = p1.sec, b = p2.sec;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << endl;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
			else if(c == b + 1){
				solve_subproblem(b);
				return;
			}
		}
		if(sz(s) == 1) {
			auto p1 = (*s.begin());
			int a = p1.sec, b = cen;
			int c;
			cout << "? " << a + 1 << " " << b + 1 << endl;
			cin >> c;
			if(c == a + 1) {
				solve_subproblem(a);
				return;
			}
		}
		cout << "! " << cen + 1 << endl;
		return;

		centroid[cen] = false;
	}
}

int N, Q;

void solve() {
	cin >> N >> Q;
	rep(i, 0, N - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		CD::add_edge(a, b, 1);
	}
	CD::solve_subproblem(0);
}

重心分解するしかないからだいぶ見通しがつきやすいですね。