P2325 [SCOI2005]王室联邦

思路

利用了树上莫队的分块方式，保证每个块的大小都\(\ge\)B且$\le$3B，然后证明略过
仅叙述一下算法的过程

使用一个栈，依次dfs这个点的每个子树，如果发现新增的节点数大于等于B，就分出新的一块，
最后把剩下的节点塞进最后一个块里

分块的代码

void dfs(int u,int f){
    int t=S.size();
    for(int i=fir[u];i;i=nxt[i]){
        if(v[i]==f)
            continue;
        dfs(v[i],u);
        if(S.size()-t>=B){
            ++block_cnt;
            core[block_cnt]=u;
            while(S.size()>t){
                belong[S.top()]=block_cnt;
                S.pop();
            }
        }
    }
    S.push(u);
}

AC代码

#include 
#include 
#include 
#include 
using namespace std;
stack S;
int v[5000],fir[5000],nxt[5000],cnt,B,n,core[5000],block_cnt=0,belong[5000];
void addedge(int ui,int vi){
    ++cnt;
    v[cnt]=vi;
    nxt[cnt]=fir[ui];
    fir[ui]=cnt;
}
void dfs(int u,int f){
    int t=S.size();
    for(int i=fir[u];i;i=nxt[i]){
        if(v[i]==f)
            continue;
        dfs(v[i],u);
        if(S.size()-t>=B){
            ++block_cnt;
            core[block_cnt]=u;
            while(S.size()>t){
                belong[S.top()]=block_cnt;
                S.pop();
            }
        }
    }
    S.push(u);
}
int main(){
    scanf("%d %d",&n,&B);
    for(int i=1;i