HDu 6394 Tree(2018 Multi-University Training Contest 7 1009)(ツリーブロック+倍増)

リンク: http://acm.hdu.edu.cn/showproblem.php?pid=6394
構想:dfsシーケンスで下の木を処理して、ブロックを分けて、私達はただ現在のこの点がこのブロックから飛び出すのに必要なステップ数と彼がこのブロックから飛び出す次の点の下の標識を維持するだけで、このように更新して尋ねる複雑度はsqrt(n)に下がって、木の上の点を照会する時私達は倍増して時間の複雑度を下げることができて、このように処理してタイムアウトすることはできません.
コードの主要な配列の作用を紹介してコードを理解しやすいです;l[i]:現在のブロックの左境界
r[i]:現在のブロックの右境界
num[i]:現在のポイントからこのブロックを飛び出すにはどのくらいのステップが必要ですか
pre[i]:この点がこのブロックから飛び出して到着した点の下付き記号は、逆ジャンプであるため、preが格納した値は、現在のブロックを飛び出して前のブロックが到着した点の下付き記号である.
tid[i]:現在の点のdfsシーケンス
Next[i]:逆さまにジャンプする(i点からこの木から飛び出すまでジャンプする)ため、Nextは現在の点から次へジャンプする点の下付き記号を格納します.
 
実装コード:

#include
using namespace std;
const int M = 1e5 + 10;
int w[M],f[21][M],n,q,head[M],pre[M],cnt,idx,num[M],Next[M],tid[M];
int block,blo[M],l[M],r[M];
struct node{
    int to,next;
}e[M];
void init(){
    cnt = 0;
    idx = 0;
    memset(head,0,sizeof(head));
}

void add(int u,int v){
    e[++cnt].to = v;e[cnt].next = head[u];head[u] = cnt;
}

void dfs(int u,int fa){  //dfs 
    f[0][u] = fa; tid[u] = ++idx;
    for(int i = head[u];i;i = e[i].next){
        dfs(e[i].to,u);
    }
}

int find(int x,int l){  //x   l      
    for(int i = 20;i >= 0;i--){
        if((l>>i)&1)
            x = f[i][x];
    }
    return x;
}

void dfs1(int u){    //   
    int p = find(u,w[u]);
    Next[tid[u]] = tid[p];
    if(tid[p] < l[blo[tid[u]]]) num[tid[u]]=1,pre[tid[u]] = tid[p];
    else num[tid[u]] = num[tid[p]]+1,pre[tid[u]] = pre[tid[p]];
    for(int i = head[u];i;i=e[i].next){
        dfs1(e[i].to);
    }
}

void update(int x,int c){  //  
    int p = find(x,c); w[x] = c;
    Next[tid[x]] = tid[p];
    if(tid[p] < l[blo[tid[x]]]) num[tid[x]] = 1,pre[tid[x]] = tid[p];
    else num[tid[x]] = num[tid[p]]+1, pre[tid[x]] = pre[tid[p]];
    for(int i = tid[x]+1;i <= r[blo[tid[x]]];i ++){
        if(Next[i] >= l[blo[i]]){
            num[i] = num[Next[i]] + 1;
            pre[i] = pre[Next[i]];
        }
    }
}

int query(int x){  //  
    int ans = 0;
    while(x > 0){
        ans += num[x];
        x = pre[x];
    }
    return ans;
}


int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        init();
        int x;
        scanf("%d",&n);
        for(int i = 2;i <= n;i ++){
            scanf("%d",&x);
            add(x,i);
        }
        for(int i = 1;i <= n;i ++)
            scanf("%d",&w[i]);
        dfs(1,0);
        for(int i = 1;i <= 20;i ++)
            for(int j = 1;j <= n;j ++)
                f[i][j] = f[i-1][f[i-1][j]];
        block  = sqrt(n);
        for(int i = 1;i <= n;i ++)  blo[i] = (i-1)/block+1;
        for(int i = 1;i <= blo[n];i ++) l[i] = (i-1)*block+1,r[i]=i*block;
        r[blo[n]] = n;
        dfs1(1);
        scanf("%d",&q);
        while(q--){
            int op,x,y;
            scanf("%d %d",&op,&x);
            if(op == 1) printf("%d
",query(tid[x]));
            else scanf("%d",&y),update(x,y);
        }
    }
    return 0;
}

 
転載先:https://www.cnblogs.com/kls123/p/9493390.html