NOI2015软件安装

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 100010
  4 #define lson (o<<1)
  5 #define rson (o<<1|1)
  6 #define mid ((l+r)>>1)
  7 int head[N],next[N*2],to[N*2],mson[N],size[N],top[N],father[N],deep[N],tot;
  8 int pos[N],sum[4*N],mark[4*N],idx;
  9 int n,q;
 10 inline void add(int f,int t){to[++tot]=t;next[tot]=head[f];head[f]=tot;}
 11 inline void pushdown(int o,int l,int r)
 12 {
 13     mark[lson]=mark[rson]=mark[o];
 14     sum[lson]=mark[o]*(mid-l+1);
 15     sum[rson]=mark[o]*(r-mid);
 16     mark[o]=-1;
 17 }
 18 inline int pushup(int o)
 19 {
 20     return sum[o]=sum[lson]+sum[rson];
 21 }
 22 void builda(int i,int f,int d)
 23 {
 24     deep[i]=d,father[i]=f,mson[i]=0,size[i]=1;
 25     for(register int j=head[i];j;j=next[j]) if(to[j]!=f)
 26     {
 27         builda(to[j],i,d+1);
 28         size[i]+=size[to[j]];
 29         if(size[mson[i]]<=size[to[j]]) mson[i]=to[j];
 30     }
 31 }
 32 
 33 void buildb(int i,int f,int t)
 34 {
 35     pos[i]=++idx;top[i]=t;
 36     buildb(mson[i],i,t);
 37     for(register int j=head[i];j;j=next[j]) if(to[j]!=f&&to[j]!=mson[i]) buildb(to[j],i,to[j]);
 38 }
 39 
 40 int query(int x,int y,int v,int o=1,int l=1,int r=idx)
 41 {
 42     if(x<=l&&r<=y) 
 43     {
 44         int ans=sum[o];
 45         sum[o]=(r-l+1)*v;
 46         mark[o]=v;
 47         return ans;
 48     }
 49     if(~mark[o]) pushdown(o,l,r);
 50     int ans=0;
 51     if(x<=mid) ans+=query(x,y,v,lson,l,mid);
 52     if(mid<y) ans+=query(x,y,v,rson,mid+1,r);
 53     pushup(o);
 54     return ans;
 55 }
 56 int askdown(int x)
 57 {
 58     int l=pos[x],r=pos[x]+size[x]-1;
 59     return query(l,r,0);
 60 }
 61 int askup(int x)
 62 {
 63     int ans=0;
 64     while(~x)
 65     {
 66         int l=pos[top[x]],r=pos[x];
 67         ans+=deep[x]-deep[top[x]]+1-query(l,r,1);
 68         x=father[top[x]];
 69     }
 70     return ans;
 71 }
 72 int main()
 73 {
 74     //freopen("hhh.in","r",stdin);
 75     memset(mark,0xff,sizeof(mark));
 76     scanf("%d",&n);
 77     for(register int i=2;i<=n;++i) 
 78     {
 79         printf("finishing");
 80         int t;
 81         scanf("%d",&t);
 82         t++;
 83         add(i,t);add(t,i);
 84     }
 85     printf("finishgraph");
 86     builda(1,0,1);
 87     buildb(1,0,1);
 88     printf("finishtree");
 89     scanf("%d",&q);
 90     while(q--)
 91     {
 92         char s[20];
 93         scanf("%s",s);
 94         if(s[0]==‘i‘) 
 95         {
 96             int x;
 97             scanf("%d",&x);x++;
 98             printf("%d\n",askup(x));
 99         }
100         else
101         {
102             int x;
103             scanf("%d",&x);x++;
104             printf("%d\n",askdown(x));
105         }
106     }
107     getchar();
108     return 0;
109 }
110     
111