bzoj 3720: Gty的妹子树

.

题意：看题目最后几行。
题解：树分块
不得不说，分块真是个神奇的东西。。
这题不是按dfs序严格分成$\sqrt n$块，而是对于每一个点，加入它的父亲的块的大小<size就归到父亲的块里，否则就新开一块。每个点记录一下它的块的根。每个块里记录下这个块里所有的值，有更新就排一下序就好了。查询时，加入这个点就是它所在块的根，那么就二分一下，再往下面的块找，否则就只看自己符不符合条件，然后往下面的点找。加入一个点和预处理差不多，判断一下属于哪个块，更新一下就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

int n,blocksize,lastans=0,m;
vector<int>te[60010],be[60010],block[60010];
struct pnt
{
    int a,tp,f;
}p[60010];

void tins(int x,int y)
{
    te[x].push_back(y);
}
void bins(int x,int y)
{
    be[x].push_back(y);
}
void dfs(int x,int f)
{
    p[x].f=f;
    if(x!=1&&block[p[f].tp].size()<blocksize)
    {
        p[x].tp=p[f].tp;
    }
    else
    {
        p[x].tp=x;
        bins(p[f].tp,x);
    }
    block[p[x].tp].push_back(p[x].a);
    for(vector<int>::iterator it=te[x].begin();it!=te[x].end();it++)
    {
        int y=*it;
        if(y==f)
        continue;
        dfs(y,x);
    }
}
int get(int x,int k)
{
    int ans=0;
    if(p[x].tp==x)
    {
        ans=block[x].end()-upper_bound(block[x].begin(),block[x].end(),k);
        for(vector<int>::iterator it=be[x].begin();it!=be[x].end();it++)
        ans+=get(*it,k);
    }
    else
    {
        if(p[x].a>k)
        ans=1;
        for(vector<int>::iterator it=te[x].begin();it!=te[x].end();it++)
        {
            if(*it!=p[x].f)
            ans+=get(*it,k);
        }
    }
//    printf("%d %d\n",x,ans);
    return ans;
}
void chg(int x,int y)
{
    vector<int>::iterator it=lower_bound(block[p[x].tp].begin(),block[p[x].tp].end(),p[x].a);
    *it=y;
    sort(block[p[x].tp].begin(),block[p[x].tp].end());
    p[x].a=y;
}
void add(int f,int a)
{
    int x=++n;
    p[x].a=a;
    p[x].f=f;
    tins(f,x);
    if(block[p[f].tp].size()<blocksize)
    p[x].tp=p[f].tp;
    else
    {
        p[x].tp=x;
        bins(p[f].tp,x);
    }
    block[p[x].tp].push_back(a);
    sort(block[p[x].tp].begin(),block[p[x].tp].end());
}
int main()
{
    scanf("%d",&n);
    blocksize=sqrt(n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        tins(x,y);
        tins(y,x);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&p[i].a);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
    sort(block[i].begin(),block[i].end());
    scanf("%d",&m);
    for(int i=0;i<m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        x^=lastans;
        y^=lastans;
        if(op==0)
        {
            printf("%d\n",lastans=get(x,y));
        }
        else if(op==1)
        {
            chg(x,y);
        }
        else
        {
            add(x,y);
        }/*
        for(int i=1;i<=n;i++)
        printf("%d ",p[i].tp);
        puts("");*/
    }
}