「SCOI2005」王室联邦

如果无法满足国王的要求，输出 ${0}$ 。否则第一行输出数 ${K}$ ，表示你给出的划分方案中省的个数，编号为 $1\dots K$ 。第二行输出 ${N}$ 个数，第 ${I}$ 个数表示编号为 ${I}$ 的城市属于的省的编号，第三行输出 ${K}$ 个数，表示这 ${K}$ 个省的省会的城市编号，如果有多种方案，你可以输出任意一种。

1
2
3
4
5
6
7
8
import java.util.Scanner;
public class Main {
    public static void main(String[] arg) {
        Scanner scanner = new Scanner(System.in);
        // todo
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>

using namespace std;

const int N=1005;

int n,b;

int cap[N],bel[N],cnt=0,stk[N],top=0;

vector<int>G[N];

inline void dfs(int x,int f){

int now=top;

for(auto to:G[x]){

if(to==f) continue;

dfs(to,x);

if(top-now>=b){

cap[++cnt]=x;

while(top!=now) bel[stk[top--]]=cnt;

}

stk[++top]=x;

}

signed main(){

ios::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

cin>>n>>b;

for(int i=1,u,v;i<n;++i){

cin>>u>>v;

G[u].emplace_back(v);

G[v].emplace_back(u);

}

dfs(1,0);

while(top) bel[stk[top--]]=cnt;

cout<<cnt<<"\n";

for(int i=1;i<=n;++i) cout<<bel[i]<<" \n"[i==n];

for(int i=1;i<=cnt;++i) cout<<cap[i]<<" \n"[i==cnt];

return 0;

}

详情