洛谷2325 [SCOI2005]王室联邦

Luogu

BZOJ

分析

树分块的入门题诶...

所以懒得写了

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,b,tot=0,sz=0;
int rt[N],belong[N],sta[N];

inline void dfs(int u,int fa) {
    int tmp=sz;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        if (sz-tmp>=b) {
            rt[++tot]=u;
            while (sz>tmp) belong[sta[sz--]]=tot;
        }
    }
    sta[++sz]=u;
}

int main() {
    n=read(),b=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    if (!tot) rt[++tot]=1;
    while (sz) belong[sta[sz--]]=tot;
    printf("%d\n",tot);
    for (re int i=1;i<=n;++i) printf("%d ",belong[i]); puts("");
    for (re int i=1;i<=tot;++i) printf("%d ",rt[i]); puts("");
    return 0;
}