ztx's Blog

/****************************************\
* Author : ztx
* Title  : bzoj 3720 Gty的妹子树
* ALG    : 分块
* CMT    :
* 我们用一次dfs过程将树分块.
* 首先, 定义根节点在块1中, 块1的size为1.
* 从根节点向下dfs, 对于当前点x, 依次遍历其儿子, 若遍历到儿子son时x所在的块的size小于Maxsize, 则将son加入x所在的块, x所在的块的size+1.
* 否则, 建立一个新块, 使son加入这个新块, 新块的size+1.
* 每遍历到一个儿子就向下dfs.
*
* 然后我们记录两个图, 一个是原来的树, 一个是块与块之间形成的图, 只需要在每次产生新块的时候加一条边即可.
* 不难发现, 块与块之间事实上形成的也是树形结构.
* 我们再对于每一个块记录下块内所有的权值, 并排序.
*
* 对于询问, 我们从当前节点向下dfs:
* 1.若遇到一个儿子不属于其所在的块, 则转到块与块之间形成的树向下搜索, 每遇到一个块就在块里二分找答案.
* 2.如果儿子依旧属于这个块, 那就直接看一下他和x的大小关系即可.
* 若令 Maxsize = sqrt(n), 这样的复杂度是O(sqrt(n)log(sqrt(n))).
* 对于加入新点, 我们直接在其父亲所在的块中加入一个点即可, 需要暴力修改权值的有序序列, 复杂度O(sqrt(n)).
* 当然如果父亲所在的块size达到了MAxsize, 就新建一个一个点的新块.
* 如果修改权值, 就直接在这个点所在的块的权值序列中暴力删除, 插入即可, 时间复杂度O(sqrt(n)).
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : bzoj 3720 Gty的妹子树
* ALG    : 分块
* CMT    :
* 我们用一次dfs过程将树分块.
* 首先, 定义根节点在块1中, 块1的size为1.
* 从根节点向下dfs, 对于当前点x, 依次遍历其儿子, 若遍历到儿子son时x所在的块的size小于Maxsize, 则将son加入x所在的块, x所在的块的size+1.
* 否则, 建立一个新块, 使son加入这个新块, 新块的size+1.
* 每遍历到一个儿子就向下dfs.
*
* 然后我们记录两个图, 一个是原来的树, 一个是块与块之间形成的图, 只需要在每次产生新块的时候加一条边即可.
* 不难发现, 块与块之间事实上形成的也是树形结构.
* 我们再对于每一个块记录下块内所有的权值, 并排序.
*
* 对于询问, 我们从当前节点向下dfs:
* 1.若遇到一个儿子不属于其所在的块, 则转到块与块之间形成的树向下搜索, 每遇到一个块就在块里二分找答案.
* 2.如果儿子依旧属于这个块, 那就直接看一下他和x的大小关系即可.
* 若令 Maxsize = sqrt(n), 这样的复杂度是O(sqrt(n)log(sqrt(n))).
* 对于加入新点, 我们直接在其父亲所在的块中加入一个点即可, 需要暴力修改权值的有序序列, 复杂度O(sqrt(n)).
* 当然如果父亲所在的块size达到了MAxsize, 就新建一个一个点的新块.
* 如果修改权值, 就直接在这个点所在的块的权值序列中暴力删除, 插入即可, 时间复杂度O(sqrt(n)).
* Time   :
\****************************************/

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std ;

#define  maxn  60010LL
#define  masz  210LL

int n , fa[maxn] = {0} ;
int data[maxn] , belong[maxn] , blccnt = 0 ;
int blc[maxn][masz] , siz[maxn] = {0} , blcsiz = 0 ;

vector<int> G[maxn] , Bc[maxn] ;

void Dfs(int u , int tp) {
int i ;
    int from = belong[u] ;
    blc[from][++siz[from]] = data[u] ;
    fa[u] = tp ;
    for (i = 0 ; i < G[u].size() ; i ++ )
        if (G[u][i] != tp) {
            if (siz[from] < blcsiz) belong[G[u][i]] = from ;
            else {
                belong[G[u][i]] = ++blccnt ;
                Bc[from].push_back(blccnt);
            }
            Dfs(G[u][i] , u) ;
        }
}
int Find(int u , int w) {
    int tmp = upper_bound(blc[u]+1 , blc[u]+siz[u]+1 , w)-blc[u]-1 ;
    return siz[u]-tmp ;
}

int QueryBlc(int u , int w) {
int i ;
    int ret = Find(u , w) ;
    for (i = 0 ; i < Bc[u].size() ; i ++ ) ret += QueryBlc(Bc[u][i] , w) ;
    return ret ;
}

int Query(int u , int tp , int w) {
int i ;
    int ret = data[u]>w ? 1 : 0 ;
    for (i = 0 ; i < G[u].size() ; i ++ )
        if (G[u][i] != tp) {
            if (belong[G[u][i]] == belong[u]) ret += Query(G[u][i] , u , w) ;
            else ret += QueryBlc(belong[G[u][i]] , w) ;
        }
    return ret ;
}

void Insert(int tp , int w) {
    int from = belong[tp] ;
    fa[++n] = tp , data[n] = w ;
    G[tp].push_back(n) , G[n].push_back(tp) ;
    if (siz[from] < blcsiz) {
        blc[belong[n] = from][++siz[from]] = data[n] ;
        sort(blc[from]+1 , blc[from]+siz[from]+1) ;
    } else {
        Bc[from].push_back(belong[n] = ++blccnt) ;
        blc[blccnt][++siz[blccnt]] = data[n] ;
    }
}

void Change(int u , int w) {
int i ;
    int from = belong[u] ;
    for (i = 1 ; i <= siz[from] ; i ++ )
        if (blc[from][i] == data[u]) {
            blc[from][i] = data[u] = w ;
            break ;
        }
    sort(blc[from]+1 , blc[from]+siz[from]+1) ;
}

void BuildBlc() {
int from ;
    blcsiz = (int)sqrt(n+0.5+log(n)/log(2)) ;
    belong[1] = ++blccnt ;
    Dfs(1 , 0) ;
    for (from = 1 ; from <= blccnt ; from ++ )
        sort(blc[from]+1 , blc[from]+siz[from]+1) ;
}

int main() {
int i , u , v , m , cmd , LAST = 0 ;
//  #define READ
    #ifdef  READ
        freopen(".in" ,"r",stdin ) ;
        freopen(".out","w",stdout) ;
    #endif
    scanf("%d", &n) ;
    for (i = 1 ; i < n ; i ++ ) {
        scanf("%d%d", &u , &v) ;
        G[u].push_back(v) , G[v].push_back(u) ;
    }
    for (u = 1 ; u <= n ; u ++ )
        scanf("%d", &data[u]) ;
    BuildBlc() ;
    scanf("%d", &m) ;
    for (i = 1 ; i <= m ; i ++ ) {
        scanf("%d%d%d", &cmd , &u , &v) ;
        u ^= LAST , v ^= LAST ;
        if (cmd == 0) printf("%d\n", LAST = Query(u , fa[u] , v)) ;
        else if (cmd == 1) Change(u , v) ;
        else Insert(u , v) ;
    }
    #ifdef  READ
        fclose(stdin) ; fclose(stdout) ;
    #else
        getchar() ; getchar() ;
    #endif
    return 0 ;
}