树上分块（块状树）
Description
我曾在弦歌之中听过你，
檀板声碎，半出折子戏。
舞榭歌台被风吹去，
岁月深处尚有余音一缕……
Gty神(xian)犇(chong)从来不缺妹子……
他来到了一棵妹子树下，发现每个妹子有一个美丽度……
由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于k的妹子个数。
某个妹子的美丽度可能发生变化……
树上可能会出现一只新的妹子……
维护一棵初始有n个节点的有根树(根节点为1)，树上节点编号为1-n，每个点有一个权值wi。
支持以下操作：
0 u x 询问以u为根的子树中，严格大于x的值的个数。(u=lastans)
1 u x 把u节点的权值改成x。(u=lastans)
2 u x 添加一个编号为"当前树中节点数+1"的节点，其父节点为u，其权值为x。(u=lastans)
最开始时lastans=0。
Input
输入第一行包括一个正整数n(1<=n<=30000)，代表树上的初始节点数。
接下来n-1行，每行2个整数u,v，为树上的一条无向边。
任何时刻，树上的任何权值大于等于0，且两两不同。
接下来1行，包括n个整数wi，表示初始时每个节点的权值。
接下来1行，包括1个整数m(1<=m<=30000)，表示操作总数。
接下来m行，每行包括三个整数 op,u,v：
op,u,v的含义见题目描述。
保证题目涉及的所有数在int内。
Output
对每个op=0，输出一行，包括一个整数，意义见题目描述。
Sample Input
2
1 2
10 20
1
0 1 5
Sample Output
2
Solution
这是一道很裸的树上分块题目(又叫块状树)。
我们设一个块的大小为Ｍ，对于一个节点，如果它的父亲所属块的大小小于Ｍ，则将该点加入其父亲的块，否则将该点加入一个新的块，并建一条从父亲块到新块的边。
在查询ｕ节点为根的子树时，对于和ｕ属于一个块的点暴力枚举，其他点则整块利用二分来计算。对于随机数据，时间复杂度可看做\(O(n * \sqrt{n} * log_n)\) ,可以接受。
Code
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define adde(u, v) (e[ecnt] = (edge){v, head[u]}, head[u] = &e[ecnt++])
#define addbe(u, v) (be[blcnt] = (edge){v, bhead[u]}, bhead[u] = &be[blcnt++])
const int maxn = 3e5 + 10, Block = 200;
int ecnt, bcnt, blcnt;
int w[maxn<<1], fa[maxn<<1], bel[maxn];
struct edge {int v; edge *next;} e[maxn<<2], *head[maxn<<1], be[maxn<<1], *bhead[maxn];
struct BLOCK {
int sz, a[Block];
void sort() {std::sort(a, a + sz);}
int find(int k) {return sz - (upper_bound(a, a + sz, k) - a);}
} B[40000];
void build(int u) {
for(edge *k = head[u]; k; k = k->next) if(fa[u] != k->v) {
int tmp;
if(B[bel[u]].sz < Block) {
tmp = bel[k->v] = bel[u];
B[tmp].a[B[tmp].sz++] = w[k->v];
}
else {
tmp = bel[k->v] = ++bcnt;
B[bcnt].a[B[bcnt].sz++] = w[k->v];
addbe(bel[u], tmp);
}
B[tmp].sort();
fa[k->v] = u;
build(k->v);
}
}
void update(int u, int v) {
int tmp = bel[u], k = lower_bound(B[tmp].a, B[tmp].a + B[tmp].sz, w[u]) - B[tmp].a;
B[tmp].a[k] = v; w[u] = v;
B[tmp].sort();
}
int bdfs(int u, int x) {
int res = B[u].find(x);
for(edge *k = bhead[u]; k; k = k->next) {
res += bdfs(k->v, x);
}
return res;
}
int pdfs(int u, int x) {
int res = 0;
if(w[u] > x) res++;
for(edge *k = head[u]; k; k = k->next) if(k->v != fa[u]) {
if(bel[u] == bel[k->v]) res += pdfs(k->v, x);
else res += bdfs(bel[k->v], x);
}
return res;
}
int query(int u, int k) {
int p, res = 0;
res += pdfs(u, k);
return res;
}
int main() {
int n, m, u, v, last = 0, op;
scanf("%d", &n);
for(int i = 1; i < n; i++) scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
fa[1] = -1, B[++bcnt].sz = 1, B[bcnt].a[0] = w[1], bel[1] = bcnt;
build(1);
scanf("%d", &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &op, &u, &v); u ^= last, v ^= last;
if(op == 0) {
printf("%d\n", last = query(u, v));
}
if(op == 1) {
update(u, v);
}
if(op == 2) {
w[++n] = v;
adde(u, n);
fa[n] = u;
int tmp;
if(B[tmp = bel[u]].sz < Block) B[tmp].a[B[tmp].sz++] = v, bel[n] = bel[u];
else B[tmp = ++bcnt].a[B[tmp].sz++] = v, addbe(bel[u], bcnt), bel[n] = bcnt;
B[tmp].sort();
}
}
return 0;
}