bzoj1086: [SCOI2005]王室联邦

求强联通分块，让其变成一棵树，对于书上每一个点（强连通分量，其内部点数为权值），对于他每一个孩子，若>k就分成一个省，省会为该点，最后再加上该点的权值，若>k，分省，否则递归上去给父亲，最后出来要特殊处理

const int N = 1010;
typedef vector<int> VI;
struct Edge {
	int v;
	Edge *Next;
	Edge() {}
	Edge(int _v, Edge *_Next) : v(_v), Next(_Next) {}
} *Fir[N];
int n, m;
int Belong[N], Head[N], Vis[N], Tot;

inline void Input() {
	scanf("%d%d", &n, &m);
	Rep(i, n - 1) {
		int x, y;
		scanf("%d%d", &x, &y);
		Fir[x] = new Edge(y, Fir[x]), Fir[y] = new Edge(x, Fir[y]);
	}
}

inline void Check(VI &Q, int &u) {
	if(sz(Q) >= m) {
		Head[++Tot] = u;
		Rep(i, sz(Q)) Belong[Q[i]] = Tot;//, printf("%d ", Q[i]);
		//printf("\n");
		Q.clear();
	}
}

inline VI Search(int u) {
	VI Q, T;
	Q.clear(), Vis[u] = 1;
	int v;
	for(Edge *Tab = Fir[u]; Tab != NULL; Tab = Tab->Next)
		if(!Vis[v = Tab->v]) {
			T = Search(v);
			/*if(u == 6) {
				Rep(i, sz(T)) printf("%d ", T[i]);
				printf("\n");
			}*/
			Q.insert(Q.end(), T.begin(), T.end()), Check(Q, u);
		}
	Q.pub(u), Check(Q, u);
	return Q;
}
inline void Solve() {
	VI Q = Search(1);
	if(Tot) {
		Rep(i, sz(Q)) Belong[Q[i]] = Tot;
		printf("%d\n", Tot);
		For(i, 1, n) printf(i < n ? "%d " : "%d\n", Belong[i]);
		For(i, 1, Tot) printf(i < Tot ? "%d " : "%d\n", Head[i]);
	} else puts("-1");
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1086");
	#endif
	Input();
	Solve();
	return 0;
}