神马品牌网铁道信号专业工资待遇:王室联邦(Royal)
来源：百度文库 编辑：神马品牌网 时间：2024/05/06 01:14:45
“余”人国的国王想重新编制他的国家。他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。
他的国家有n个城市，编号为1..n。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。为了防止管理太过分散，每个省至少要有B个城市，为了能有效的管理，每个省最多只有3B个城市。
每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。
一个城市可以作为多个省的省会。
聪明的你快帮帮这个国王吧！
输入文件：
第一行包含两个数N，B（1<=N<=1000, 1 <= B <= N）。接下来N－1行，每行描述一条边，包含两个数，即这条边连接的两个城市的编号。
输出文件：
如果无法满足国王的要求，输出0。否则第一行输出数K，表示你给出的划分方案中省的个数，编号为1..K。第二行输出N个数，第I个数表示编号为I的城市属于的省的编号，第三行输出K个数，表示这K个省的省会的城市编号，如果有多种方案，你可以输出任意一种。
Sample Input
8 2
1 2
2 3
1 8
8 7
8 6
4 6
6 5
Sample Output
3
2 1 1 3 3 3 3 2
2 1 8
{$R-,S-,Q-}
{$M 65520,0,655360}
Const fin = 'royal.in';
fon = 'royal.out';
MaxN = 1001;
Var e : array[0..MaxN * 2, 1..2] of integer;{边集数组}
g : array[0..MaxN * 2] of integer;
num, start, fa, center, colour, stack, count : array[0..MaxN * 2] of integer;
n, b, b3, kind, top, cut : integer;
Procedure Init;{输入}
var i : integer;
begin
assign(input, fin); reset(input);
read(n, b); b3 := b + b + b;
for i := 1 to n - 1 do begin
read(e[i, 1], e[i, 2]);
inc(num[e[i, 1]]); inc(num[e[i, 2]]);
end;
close(input);
start[1] := 1; start[n + 1] := n + n - 1;
for i := 2 to n do start[i] := start[i - 1] + num[i - 1];
num := start;
for i := 1 to n - 1 do begin
g[num[e[i, 1]]] := e[i, 2]; inc(num[e[i, 1]]);
g[num[e[i, 2]]] := e[i, 1]; inc(num[e[i, 2]]);
end;
end;
Procedure Print;{输出}
var i : integer;
begin
inc(kind); center[kind] := 1;
for i := 1 to n do if colour[i] = 0 then colour[i] := kind;
assign(output, fon); rewrite(output);
writeln(kind);
for i := 1 to n do write(colour[i], ' '); writeln;
for i := 1 to kind do write(center[i], ' '); writeln;
close(output);
halt;
end;
Procedure Search(i : integer);{主过程}
var j, temp : integer;
begin
inc(top); stack[top] := i; count[i] := 1;
for j := start[i] to start[i + 1] - 1 do if g[j] <> fa[i] then begin{递归遍历子树}
fa[g[j]] := i;
Search(g[j]);
inc(count[i], count[g[j]]);
end;
if n - cut <= b3 then Print;{剩下部分已不超过}
j := start[i + 1];{3b则划分后输出 }
while count[i] > b do begin
temp := 0;
while temp < b do begin
dec(j);
if g[j] <> fa[i] then inc(temp, count[g[j]]);
end;
dec(count[i], temp); inc(cut, temp);{划分出一个省，省会}
inc(kind); center[kind] := i;{为当前子树的根结点}
while stack[top] <> g[j] do begin
colour[stack[top]] := kind;
dec(top);
end;
colour[stack[top]] := kind; dec(top);
if n - cut <= b3 then Print;
end;
end;
Begin
Init;
Search(1);
End.