BZOJ-1086 [SCOI2005]王室联邦（树分块）

递归处理子树，把当前结点当作栈底，然后递归，回溯回来之后如果栈中结点数量到达某一个标准时，弹出栈中所有的元素分到一个块中，最后递归结束了如果栈中还有元素，那么剩下的这些元素放在新的块中

当块中元素大于B时，立即释放放入到一个新块中，省会可以直接用当前递归到的点，因为它的子节点一定是在栈中的。最后栈中剩下的部分是小于B的，所以可以直接加到上一个块中。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1010;

vector<int> G[N];

int n,B,st[N],sz = 0;

int block_cnt = 0,province[N],be[N];

void dfs(int u,int fa = -1){

    int bottom = sz;//把当前结点当作栈底

    for(int i = 0;i < G[u].size();i++){

        int y = G[u][i];

        if(y == fa)continue;

        dfs(y,u);

        if(sz - bottom >= B){//如果栈中元素大于B

            block_cnt++;//块数++

            while(sz != bottom){

                be[st[sz--]] = block_cnt;

            }

            province[block_cnt] = u;

        }

    }

    st[++sz] = u;//栈中加入该元素

}

int main(){

    scanf("%d%d",&n,&B);

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

        int x,y;scanf("%d%d",&x,&y);

        G[x].push_back(y);

        G[y].push_back(x);

    }

    dfs(1);

    while(sz)be[st[sz--]] = block_cnt;

    printf("%d\n",block_cnt);

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

        printf("%d ",be[i]);

    }

    puts("");

    for(int i=1;i<=block_cnt;i++){

        printf("%d ",province[i]);

    }

    puts("");

    return 0;

}

巴特西

BZOJ-1086 [SCOI2005]王室联邦（树分块）

最新文章

热门文章

巴特西

BZOJ-1086 [SCOI2005]王室联邦 （树分块）

最新文章

热门文章

BZOJ-1086 [SCOI2005]王室联邦（树分块）