hdu6394 Tree dfs序+分块

题目连接：Tree

题意：跟弹飞绵羊差不多这题是在树上条，给你一颗树，每个点上有个值w，当你走到这会直接跳到向上走w步的父亲节点（如过没有就算跳出去了）然后两种操作。

一种询问从x跳出要多少步。第二种修改某个点的w.

题解，先dfs一次的到dfs序，然后按dfs序分块，有cn保存它跳出这一块需要的次数，net保存跳出这块会去的点。然后就都是暴力了。复杂度nsqrt(n);

  1 #include<bits/stdc++.h>
  2 #define ll long long
  3 using namespace std;
  4 const int N = 1e5+10;
  5 int w[N];//
  6 int fa[20][N];
  7 int n,m;
  8 int head[N],nxt[N],to[N],cnt;//链表存边,cnt边数
  9 int id[N],tot;//dfs序
 10 int num,block,belong[N],l[N],r[N];//块的数目,快的大小，属于那块，每块的左右边界
 11 int cn[N],net[N],pre[N];//跳出本块的次数,跳向的下一块的点,这个点会跳向的位置
 12 void init()//初始化
 13 {
 14     memset(head,0,sizeof(head));
 15     cnt=0;
 16     tot=0;
 17 }
 18 void add_edge(int v,int u)//加v到u的单向边
 19 {
 20     to[++cnt]=u;nxt[cnt]=head[v]; head[v]=cnt;
 21 }
 22 void dfs(int v,int f)//dfs一次,得到dfs序和每一个点的父亲
 23 {
 24     fa[0][v]=f;id[v]=++tot;
 25     for(int i=head[v];i;i=nxt[i])
 26     {
 27         dfs(to[i],v);
 28     }
 29 }
 30 void built()//分块
 31 {
 32     block=sqrt(n);
 33     num=n/block;if(n%block)num++;
 34     for(int i=1;i<=n;i++)
 35     {
 36         belong[i]=((i-1)/block)+1;
 37     }
 38     for(int i=1;i<=num;i++)
 39     {
 40         l[i]=(i-1)*block+1;r[i]=i*block;
 41     }
 42     r[num]=n;
 43 }
 44 int find(int x,int l)//x向上走l步会到那里
 45 {
 46     int p=x;
 47     for(int i=19;i>=0;i--)
 48     {
 49         if((l>>i)&1)
 50         {
 51             x=fa[i][x];
 52         }
 53     }
 54     return x;
 55 }
 56 void dfs2(int v)//再次dfs得到cn[N],net[N],pre[N]
 57 {
 58     int p=find(v,w[v]);
 59     pre[id[v]]=id[p];
 60     if(id[p]<l[belong[id[v]]])cn[id[v]]=1,net[id[v]]=id[p];
 61     else cn[id[v]]=cn[id[p]]+1,net[id[v]]=net[id[p]];
 62      for(int i=head[v];i;i=nxt[i])
 63     {
 64         dfs2(to[i]);
 65     }
 66 }
 67 int query(int x)
 68 {
 69     int ans=0;
 70     while(x>0)
 71     {
 72         ans+=cn[x];
 73         x=net[x];
 74     }
 75     return ans;
 76 }
 77 void update(int x,int v)
 78 {
 79     int p=find(x,v);w[x]=v;
 80     pre[id[x]]=id[p];
 81     if(id[p]<l[belong[id[x]]])cn[id[x]]=1,net[id[x]]=id[p];
 82     else cn[id[x]]=cn[id[p]]+1,net[id[x]]=net[id[p]];
 83     for(int i=id[x]+1;i<=r[belong[id[x]]];i++)//更新这块内后面的点
 84     {
 85         if(pre[i]>=l[belong[i]])
 86         {
 87             cn[i]=cn[pre[i]]+1;
 88             net[i]=net[pre[i]];
 89         }
 90     }
 91 }
 92 int main(){
 93     int T;
 94     scanf("%d",&T);
 95     while(T--)
 96     {
 97         init();
 98         scanf("%d",&n);
 99         for(int i=2;i<=n;i++)
100         {
101             int x;
102             scanf("%d",&x);
103             add_edge(x,i);
104         }
105         for(int i=1;i<=n;i++)
106         {
107             scanf("%d",&w[i]);
108         }
109         dfs(1,0);
110         for(int i=1;i<20;i++)
111         {
112             for(int j=1;j<=n;j++)
113             {
114                 fa[i][j]=fa[i-1][fa[i-1][j]];
115             }
116         }
117         built();
118         dfs2(1);
119         scanf("%d",&m);
120         while(m--)
121         {
122             int op,x,v;
123             scanf("%d %d",&op,&x);
124             if(op==1)
125             {
126                 printf("%d
",query(id[x]));
127             }
128             else
129             {
130                 scanf("%d",&v);
131                 update(x,v);
132             }
133         }
134     }
135 }