好珂怕……

树分块是什么东西啊……感觉好暴力……

直接贴一下好了->

1 //minamoto  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 using namespace std;  8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)  9 char buf[1<<21],*p1=buf,*p2=buf; 10 template
          
           inline bool cmax(T&a,const T&b){ return a
           
            1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 25 while(z[++Z]=x%10+48,x/=10); 26 while(sr[++C]=z[Z],--Z);sr[++C]='\n'; 27 } 28 const int N=60005,SIZE=305; 29 int head[N],Next[N<<1],ver[N<<1],tot; 30 inline void add(int u,int v){ 31 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 32 } 33 int n,m,cnt,w[N],bh[N],bt,fa[N],belong[N],bn[N<<1],bv[N<<1]; 34 struct Block{ 35 vector
            
              a; 36 Block(){a.clear();} 37 inline void ins(int x){ 38 a.push_back(x); 39 for(int i=a.size()-1;i;--i) 40 if(a[i-1]>a[i]) swap(a[i-1],a[i]);else break; 41 } 42 inline void update(int x,int k){ 43 int pos=lower_bound(a.begin(),a.end(),x)-a.begin(); 44 a[pos]=k; 45 for(int i=pos;i;--i) 46 if(a[i-1]>a[i]) swap(a[i-1],a[i]);else break; 47 for(int i=pos,s=a.size()-1;i
             
              a[i+1]) swap(a[i],a[i+1]);else break; 49 } 50 inline int query(int x){ 51 return a.end()-upper_bound(a.begin(),a.end(),x); 52 } 53 }bl[N]; 54 inline void add_bl(int u,int v){ 55 bv[++bt]=v,bn[bt]=bh[u],bh[u]=bt; 56 } 57 void dfs(int u,int f){ 58 fa[u]=f; 59 if(bl[belong[f]].a.size()==SIZE){ 60 belong[u]=++cnt; 61 bl[cnt].ins(w[u]); 62 add_bl(belong[f],cnt); 63 } 64 else{ 65 belong[u]=belong[f],bl[belong[u]].ins(w[u]); 66 } 67 for(int i=head[u];i;i=Next[i]){ 68 if(ver[i]!=f) dfs(ver[i],u); 69 } 70 } 71 int dfsbl(int u,int k){ 72 int ans=bl[u].query(k); 73 for(int i=bh[u];i;i=bn[i]) 74 ans+=dfsbl(bv[i],k); 75 return ans; 76 } 77 int dfsans(int u,int k){ 78 int ans=w[u]>k?1:0; 79 for(int i=head[u];i;i=Next[i]){ 80 int v=ver[i]; 81 if(v==fa[u]) continue; 82 if(belong[v]==belong[u]) ans+=dfsans(v,k); 83 else ans+=dfsbl(belong[v],k); 84 } 85 return ans; 86 } 87 int main(){ 88 //freopen("testdata.in","r",stdin); 89 n=read(); 90 for(int i=1;i