WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
树分块的姿势
树分块的姿势

树分块的时候应该保证,以下的几点:
1. 对于一个块内的所有深度最小的节点的父节点相同(根节点除外)
3. 每一个块内深度非最小的节点的父亲节点一定与其在同一个块内
2. 一个块的大小在[BLOCKSIZE, 3\cdot BLOCKSIZE]之间

这样的好处在于分块之后,所有块基本上都是联通的。如果不联通,加入深度最小的节点的父亲之后,这个块就联通了。

struct Edge{
    int v, nxt;
    Edge(){}
    Edge(int v0, int n0){
        v=v0;
        nxt=n0;
    }
}e[MAXN];
int head[MAXN], nume;

int stk[MAXN], top;
int siz[MAXN], bel[MAXN], cap[MAXN], cnt;
int BLOCKSIZE;

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

void dfs(int x){
    stk[++top]=x;
    for (int i=head[x]; i; i=e[i].nxt){
        int v=e[i].v;
        dfs(v);
        siz[x]+=siz[v];
        if (siz[x]>=BLOCKSIZE){
            siz[x]=0;
            cap[++cnt]=x;
            while(stk[top]!=x) bel[stk[top--]]=cnt;
        }
    }
    siz[x]++;
}

void divTree(int x, int z){
    if (bel[x]) z=bel[x]; else bel[x]=z;
    for (int i=head[x]; i; i=e[i].nxt) divTree(e[i].v, z);
}

例题:BZOJ 1086(直接分块), HDU 6394(树上弹飞绵羊)

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

树分块的姿势
树分块的时候应该保证,以下的几点: 1. 对于一个块内的所有深度最小的节点的父节点相同(根节点除外) 3. 每一个块内深度非最小的节点的父亲节点一定与其在同一个块内 2. 一个块的大小在…
扫描二维码继续阅读
2018-08-14
<--! http2https -->