[JLOI2014]松鼠的新家

  1 #include<bits/stdc++.h>
  2 
  3 #define mid ((l+r)>>1)
  4 #define ll long long
  5 
  6 using namespace std;
  7 const int N=270020;
  8 
  9 int n,m,r,cnt,tot;
 10 int a[N<<2],mark[N<<2];
 11 int siz[N<<2],dep[N<<2],top[N<<2],f[N<<2],son[N<<2];
 12 int head[N<<2],nxt[N<<2],to[N<<2];
 13 int wt[N<<2],w[N<<2],id[N<<2];
 14 
 15 void add(int x,int y)
 16 {
 17     cnt++;
 18     to[cnt]=y;
 19     nxt[cnt]=head[x];
 20     head[x]=cnt;
 21 //f[cnt]=x;
 22     return ;
 23 }
 24 //--------------------------//
 25 //  《  线  段  树  》     //
 26 void build(int x,int l,int r)
 27 {
 28     //建树 
 29      if(l==r)
 30     {
 31         a[x]=wt[l];
 32    
 33         return;
 34     }
 35     build(x<<1,l,mid);
 36     build((x<<1)|1,mid+1,r);
 37 
 38     a[x]=a[x<<1]+a[(x<<1)|1];
 39    
 40     return ;
 41 }
 42 
 43 void addx(int x,int l,int r,int k)
 44 {//标记 
 45     a[x]+=(r-l+1)*k;
 46    
 47     mark[x]+=k;
 48 
 49     return ;
 50 }
 51 
 52 void push(int x,int l,int r)
 53 {//推标记 
 54     addx(x<<1,l,mid,mark[x]);
 55     addx((x<<1)|1,mid+1,r,mark[x]);
 56     mark[x]=0;
 57 
 58     return ;
 59 }
 60 void pl(int x,int l,int r,int s,int e,int k)
 61 {
 62     //区间加 
 63     if(r<s||l>e)return ;
 64     if(s<=l&&e>=r)
 65     {
 66         addx(x,l,r,k);
 67         return ;
 68     }
 69     push(x,l,r);
 70     pl((x<<1),l,mid,s,e,k);
 71     pl((x<<1)|1,mid+1,r,s,e,k);
 72    
 73 
 74     return ;
 75 }
 76 
 77 int que(int x,int l,int r,int s,int e)
 78 {//查询区间值 
 79     if(r<s||l>e)
 80     return 0;
 81     if(s<=l&&e>=r)
 82     return a[x];
 83     push(x,l,r);
 84     return (que((x<<1),l,mid,s,e)+que((x<<1)+1,mid+1,r,s,e));
 85 }
 86 //--------------------------//
 87 void dfs1(int x,int fa,int deep)
 88 {
 89     f[x]=fa;
 90     siz[x]=1;
 91     dep[x]=deep;
 92     int maxson=-1;
 93     for(int i=head[x];i;i=nxt[i])
 94     {
 95         int y=to[i];
 96         if(y==fa)
 97         continue;
 98         dfs1(y,x,deep+1);
 99        
100         siz[x]+=siz[y];
101         if(siz[y]>maxson)
102         {
103             son[x]=y;
104             maxson=siz[y];
105         }
106     }
107 
108     return ;
109 }
110 
111 void dfs2(int x,int topf) 
112 {
113     tot++;
114     id[x]=tot;
115     wt[tot]=w[x];
116     top[x]=topf;
117 
118     if(!son[x])
119     return ;
120     dfs2(son[x],topf);
121     for(int i=head[x];i;i=nxt[i])
122     {
123         int y=to[i];
124         if(y==f[x]||y==son[x])
125         continue;
126 
127         dfs2(y,y);
128     }
129 
130     return ;
131 }
132 
133 
134 void upr(int x,int y,int k)
135 {
136     while(top[x]!=top[y])
137     {
138         if(dep[top[x]]<dep[top[y]])
139         swap(x,y);
140         pl(1,1,n,id[top[x]],id[x],k); 
141         x=f[top[x]];
142     }
143     if(dep[x]>dep[y])
144     swap(x,y);
145     pl(1,1,n,id[x],id[y],k);
146 
147     return ;
148 }
149 
150 
151 int main()
152 {
153     ios::sync_with_stdio(false);
154     cin>>n;
155     r=1;
156     for(int i=1;i<=n;i++)
157     cin>>w[i];
158     for(int i=1;i<n;i++)
159     {   
160     int q,e; 
161         cin>>q>>e;
162         add(q,e);
163         add(e,q);
164     }
165     dfs1(r,0,1);
166     dfs2(r,r);
167  
168         for(int i=1;i<=n-1;i++)
169         {
170         upr(w[i],w[i+1],1);
171         upr(w[i+1],w[i+1],-1);
172     }
173     for(int i=1;i<=n;i++)
174     cout<<que(1,1,n,id[i],id[i])<<endl;
175 
176     return 0;
177 }