这道题还有一种分块的做法：每当发现当前子树中有K个点，就将这K个点合在一起，然后把每个块内的节点权值排序（虽然这个算法并没有保证块的个数，但是由于数(shen)据(qi)随(hai)机(luo)，所以不妨设为n/K）。

操作0：对于每一个块暴力查询（构建一颗虚树），然后对根所在块暴力，时间复杂度o(K+n/K)。

操作1：暴力修改该权值并排序（可以插入，也可以直接sort）

操作2：当添加节点父亲所在块节点个数不到K，直接加入该块，否则单独成块，注意维护节点信息。

1 #include
      
        2 using namespace std; 3 #define siz 300 4 #define N 100005 5 struct ji{ 6     int nex,to; 7 }edge[N<<1]; 8 int E,n,m,x,y,s,p,z,ans,head[2][N],bl[N],f[N],w[N],se[N/3][siz+10]; 9 void add(int x,int y,int p){10     edge[E].nex=head[p][x];11     edge[E].to=y;12     head[p][x]=E++;13 }14 void dfs(int k,int fa){15     f[k]=fa;16     if (se[bl[fa]][0]==siz)add(bl[fa],++s,1);17     bl[k]=s;18     se[s][++se[s][0]]=w[k];19     for(int i=head[0][k];i!=-1;i=edge[i].nex)20         if (edge[i].to!=fa)dfs(edge[i].to,k);21 }22 void dfs2(int k){23     ans+=se[k]+se[k][0]+1-upper_bound(se[k]+1,se[k]+se[k][0]+1,y);24     for(int i=head[1][k];i!=-1;i=edge[i].nex)dfs2(edge[i].to);25 }26 void calc(int k,int fa,int p){27     if (bl[k]!=p){28         dfs2(bl[k]);29         return;30     }31     if (w[k]>y)ans++;32     for(int i=head[0][k];i!=-1;i=edge[i].nex)33         if (edge[i].to!=fa)calc(edge[i].to,k,p);34 }35 int main(){36     scanf("%d",&n);37     memset(head,-1,sizeof(head));38     for(int i=1;i