POJ 2114: Boatherds

http://poj.org/problem?id=2114

蟻本と同じことやるだけ…と思うがO(MNlog^2N)になって通るわけないだろ!と思い、ググってみるとどうやらそれでいけるらしいと分かったので、submitしてみるとTLE。途方に暮れているとvectorにstaticつけると速くなるよって書いてあったのでつけてみると余裕でAC。わけわからん。

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 update(int s);

	bool solve_subproblem(int v) {
		if(ans > 0) return true;
		compute_subtree_size(v, -1);
		int s = search_centroid(v, -1, subtree_size[v]).sec;
		centroid[s] = true;

		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;
			solve_subproblem(G[s][i].to);
		}
		update(s);
		centroid[s] = false;
		return ans > 0;
	}

	////////////////////////////////////////////// edit from here
	
	//distance from centroid
	void enumerate_pathes(int v, int p, int d, vi &ds) {
		ds.push_back(d);
		rep(i, 0, (int)G[v].size()) {
			int w = G[v][i].to;
			if(w == p || centroid[w]) continue;
			enumerate_pathes(w, v, d + G[v][i].length, ds);
		}
	}

	//num of pairs whose lengths is less than k
	int count_pairs(vi &ds) {
		int res = 0;
		sort(ds.begin(), ds.end());
		int j = (int)ds.size();
		rep(i, 0, (int)ds.size()) {
			while(j > 0 && ds[i] + ds[j - 1] > K) j--;
			res += j - (j > i ? 1 : 0);
		}
		j = (int)ds.size();
		rep(i, 0, (int)ds.size()) {
			while(j > 0 && ds[i] + ds[j - 1] >= K) j--;
			res -= j - (j > i ? 1 : 0);
		}
		return res;
	}

	void update(int s) {
		static vi ds;
		ds.clear();
		ds.push_back(0);
		rep(i, 0, (int)G[s].size()) {
			if(centroid[G[s][i].to]) continue;

			static vi tds;
			tds.clear();
			enumerate_pathes(G[s][i].to, s, G[s][i].length, tds);

			ans -= count_pairs(tds);
			ds.insert(ds.end(), tds.begin(), tds.end());
		}
		ans += count_pairs(ds);
	}
}


int main() {
	while(true) {
		scanf("%d", &N);
		CD::init(N);
		if(N == 0) break;
		rep(i, 0, N) {
			while(true) {
				int a, b;
				scanf("%d", &a); if(a == 0) break;
				a--;
				scanf("%d", &b);
				CD::add_edge(i, a, b);
			}
		}
		while(true) {
			ans = 0;
			scanf("%d", &K);
			if(K == 0) break;
			if(CD::solve_subproblem(0)) printf("AYE\n");
			else printf("NAY\n");
		}
		printf(".\n");
	}
	return 0;
}

c++もっと詳しくならないとと思った。