BZOJ 1086: [SCOI2005]王室联邦 [树上分块]

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

portal

题意：

树分成若干块大小在$[s,3s]$之间，每块有一个根(可以不在块内)，所有点到根路径上的点都必须在块内

据说这是一个保证了 块大小直径个数 的科学分块方法，貌似只有本题有用我错了原来是树上莫队可以用啊....

做法是，dfs并维护一个栈，dfs到某一个点考虑从子树中找以它为根的块，当遍历某一棵子树结束时栈中元素$\ge s$就分成一块

可以保证块的大小$\le 2s$，因为假如这个子树结束后为$s-1$，而下一个子树最多再贡献$s$个点

处理完当前点再把当前点入栈

dfs结束后还有一些点没有块，这些点一定$<s$，直接分入最后一块就行了

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,s;

struct edge{int v,ne;}e[N<<];

int cnt,h[N];

inline void ins(int u,int v){

    e[++cnt]=(edge){v,h[u]}; h[u]=cnt;

    e[++cnt]=(edge){u,h[v]}; h[v]=cnt;

}

int st[N],top, pos[N],m,root[N];

void dfs(int u,int fa){

    int bot=top;

    for(int i=h[u];i;i=e[i].ne) if(e[i].v!=fa) {

        dfs(e[i].v, u);

        if(top-bot>=s){

            root[++m]=u;

            while(top!=bot) pos[st[top--]]=m;

        }

    }

    st[++top]=u;

}

int main(){

    freopen("in","r",stdin);

    n=read();s=read();

    for(int i=;i<n;i++) ins(read(), read());

    dfs(,);

    while(top) pos[st[top--]]=m;

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

    for(int i=;i<=n;i++) printf("%d%c",pos[i], i==n?'\n':' ');

    for(int i=;i<=m;i++) printf("%d%c",root[i],i==m?'\n':' ');

    return ;

}