HDU - 6394 Tree（树分块+倍增+dfs序）

た入场券 2021-12-03 06:29 215阅读 0赞

## 题意：给出一棵树，然后每个节点有一个权值，代表这个点可以往上面跳多远，问最少需要多少次可以跳出这颗树。 ##

## 分析：树上弹飞绵羊，利用dfs序把树上节点变成连续区间序列，先dfs一次得到dfs序，然后按dfs序分块。倍增计算从某点跳x到哪个点，用cn保存它跳出这一块需要的次数，ne保存跳出这块会去的点。然后块内就暴力修改了。复杂度n\*sqrt(n)。 ##

## 参考：[https://www.cnblogs.com/fht-litost/p/9557863.html。][https_www.cnblogs.com_fht-litost_p_9557863.html] ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 10;
    
    int w[N],fa[20][N],n,m;
    int head[N],nxt[N],to[N],tot;
    int id[N],cnt;//dfs序
    int num,block,belong[N],l[N],r[N];//块的数目,快的大小，属于那块，每块的左右边界
    int cn[N],ne[N],pre[N];//跳出本块的次数,跳向的下一块的点,这个点会跳向的位置
    
    void init(){
        memset(head,-1,sizeof(head));
        cnt=tot=0;
    }
    void addedge(int u,int v){
        to[tot]=v;
        nxt[tot]=head[u];
        head[u]=tot++;
    }
    void dfs1(int u,int f){///dfs一次,得到dfs序和每一个点的父亲
        fa[0][u]=f;
        id[u]=++cnt;
        for(int i=head[u];~i;i=nxt[i]){
            dfs1(to[i],u);
        }
    }
    void build(){///分块预处理
        block=sqrt(n);
        num=(n+block-1)/block;
        for(int i=1;i<=n;i++){
            belong[i]=(i-1)/block+1;
        }
        for(int i=1;i<=num;i++){
            l[i]=(i-1)*block+1;
            r[i]=i*block;
        }
        r[num]=n;
    }
    int find(int u,int l){
        for(int i=19;i>=0;i--){
            if((l>>i)&1){
                u=fa[i][u];
            }
        }
        return u;
    }
    void dfs2(int u){///再次dfs得到cn[N],net[N],pre[N]
        int f=find(u,w[u]);
        pre[id[u]]=id[f];
        if(id[f]<l[belong[id[u]]]) cn[id[u]]=1,ne[id[u]]=id[f];
        else cn[id[u]]=cn[id[f]]+1,ne[id[u]]=ne[id[f]];
        for(int i=head[u];~i;i=nxt[i]){
            dfs2(to[i]);
        }
    }
    int query(int u){
        int ans=0;
        while(u>0){
            ans+=cn[u];
            u=ne[u];
        }
        return ans;
    }
    void update(int u,int val){///暴力更新本块修改节点之前部分的值
        int f=find(u,val);
        w[u]=val;
        pre[id[u]]=id[f];
        if(id[f]<l[belong[id[u]]]) cn[id[u]]=1,ne[id[u]]=id[f];
        else cn[id[u]]=cn[id[f]]+1,ne[id[u]]=ne[id[f]];
        for(int i=id[u]+1;i<=r[belong[id[u]]];i++){//更新这块内后面的点
            if(pre[i]>=l[belong[i]]){
                cn[i]=cn[pre[i]]+1;
                ne[i]=ne[pre[i]];
            }
        }
    }
    int main() {
        int T,x;
        scanf("%d",&T);
        while(T--){
            init();
            scanf("%d",&n);
            for(int i=2;i<=n;i++){
                scanf("%d",&x);
                addedge(x,i);
            }
            for(int i=1;i<=n;i++) scanf("%d",&w[i]);
            dfs1(1,0);
            for(int i=1;i<20;i++)
                for(int j=1;j<=n;j++)
                    fa[i][j]=fa[i-1][fa[i-1][j]];
            build();
            dfs2(1);
            scanf("%d",&m);
            while(m--){
                int op,x,y;
                scanf("%d%d",&op,&x);
                if(op==1) printf("%d\n",query(id[x]));
                else {
                    scanf("%d",&y);
                    update(x,y);
                }
            }
        }
        return 0;
    }

[https_www.cnblogs.com_fht-litost_p_9557863.html]: https://www.cnblogs.com/fht-litost/p/9557863.html