Andrew Stankevich’s Contest #3解题报告 » ZOJ2368

ZOJ2368
ZOJ2368.cpp


#include <queue>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

const int MAXN = 10101;

int n, b;
int s[MAXN];
vector<int> c, e[MAXN];

int dfs(int p) {
	s[p] = 1;
	for (size_t i = 0; i < e[p].size(); ++i) {
		if (s[e[p][i]] == 0) {
			s[p] += dfs(e[p][i]);
		}
	}
	return s[p];
}

void dfs(int p, int r) {
	// assert(r < 0);
	s[p] = r;
	for (size_t i = 0; i < e[p].size(); ++i) {
		if (s[e[p][i]] > 0) {
			dfs(e[p][i], r);
		}
	}
}

int gao(int p, int r) {
	int ret;
	queue<pair<int, int> > q;
	vector<pair<int, int> > v;

	// assert(r < b);
	// assert(s[p] >= b);
	// printf("gao %d\n", p);
	s[p] = 0;
	if (r > 0) {
		v.push_back(make_pair(r, -1));
	}
	for (size_t i = 0; i < e[p].size(); ++i) {
		if (s[e[p][i]] > 0) {
			v.push_back(make_pair(s[e[p][i]], e[p][i]));
		}
	}
	sort(v.begin(), v.end());

	int pos = 0, sum = 0;

	// puts("A");
	while (pos < (int)v.size() && v[pos].first < b) {
		sum += v[pos].first;
		q.push(v[pos]);
		if (sum >= 3 * b) {
			c.push_back(p);
			do {
				sum -= q.front().first;
				if (q.front().second == -1) {
					ret = -c.size();
				} else {
					dfs(q.front().second, -c.size());
				}
				q.pop();
			} while (sum > 2 * b);
			// sum \in [b, 2b]
		}
		++pos;
	}
	// puts("B");
	if (sum + 1 < b) {
		// assert(pos != (int)v.size());
		r = sum + 1;
		v.back().first += r;
	} else {
		r = 0;
		c.push_back(p);
		s[p] = -c.size();
	}
	// puts("C");
	while (pos < (int)v.size()) {
		if (r > 0 && pos == (int)v.size() - 1) {
			if (v[pos].first > 3 * b) {
				s[p] = gao(v[pos].second, r);
			} else {
				c.push_back(p);
				dfs(v[pos].second, -c.size());
				s[p] = -c.size();
			}
		} else if (v[pos].first > 3 * b) {
			gao(v[pos].second, 0);
		} else {
			c.push_back(p);
			dfs(v[pos].second, -c.size());
		}
		++pos;
	}
	// puts("D");
	while (!q.empty()) {
		if (q.front().second == -1) {
			ret = s[p];
		} else {
			dfs(q.front().second, s[p]);
		}
		q.pop();
	}

	return ret;
}

int main() {
	int re;
	int x, y;

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d%d", &n, &b);
		for (int i = 1; i <= n; ++i) {
			s[i] = 0;
			e[i].clear();
		}
		for (int i = 1; i < n; ++i) {
			scanf("%d%d", &x, &y);
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1);
		c.clear();
		gao(1, 0);
		printf("%d\n", (int)c.size());
		for (int i = 1; i <= n; ++i) {
			printf("%d%c", -s[i], (i == n) ? '\n' : ' ');
		}
		for (size_t i = 0; i < c.size(); ++i) {
			printf("%d%c", c[i], (i == c.size() - 1) ? '\n' : ' ');
		}
	}

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1812566 	2009-04-01 05:30:20 	Accepted 	2368 	C++ 	170 	6168 	watashi@Zodiac
Leave a Reply