题解 P2325 【[SCOI2005]王室联邦】

Tgotp · 2017-06-26 16:09:57 · 题解

算法：树分块；

思路：首先，对于整个树dfs，当子树的大小大于 b 时，就将它们分在一块，同时令首都为当前这个点，容易想到：对于根，可能会剩下一些点，于是将这些点分在最后一个块里，容易发下，最后这一堆与那一块之和一定小于3b，正确性得证。

ok c++代码如下：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
#include<cmath>
#include<queue>
using namespace std; 
const int N = 1e3+1; 
int head[N],tot,n,b,sz,be[N],stk[N],root[N],cnt;
inline void read(int&x){
    x = 0;int sign = 1;char c;
    do{ c = getchar();if(c == '-') sign = -1; }while(c < '0' || c >'9');
    do{ x = x*10 + c - '0';c = getchar(); }while(c <= '9' && c >='0');
    x*=sign;
}
struct node
{
    int to,next;
}edge[N * 2];
inline void add(int a,int b)
{
    edge[tot].next = head[a];
    edge[tot].to   = b;
    head[a] = tot ++;
}
void dfs(int u,int fa)
{
    int bottom = sz;
    for(int i = head[u]; ~i ; i = edge[i].next)
    {
        node&e = edge[i];
        if(e.to == fa) continue;
        dfs(e.to,u);
        if(sz - bottom >= b){
            cnt++;
            root[cnt] = u;
            while(sz > bottom) be[stk[sz--]] = cnt;
        }
    }
    stk[++sz] = u;
}
int main()
{
    memset(head,-1,sizeof(head));
    read(n);read(b);
    int u, v;
    for(int i = 1 ;i < n;i++)
    {
        read(u);read(v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    while(sz) be[stk[sz--]] = cnt;
    cout<<cnt<<endl;
    for(int i = 1;i <= n;i++) printf("%d ",be[i]);puts("");
    for(int i = 1;i <= cnt;i++) printf("%d ",root[i]);
    return 0;
}
推广blog：<http://tgotp.science>