点分树

说在前面的

我一看到是点分树，马上就点进来了，很快啊。前置知识：点分治。

约定
- $dis(u,v)$ 表示 $u,v$ 的树上路径长度。

引入

给出一颗 $n$ 个点的树，每个点有一个权值，有两种操作，一种是将某个点的权值修改为 $v$ ，另一种是查询距离点 $u$ 不超过 $d$ 的点的权值和。

分析

我们考虑暴力，如果将一个操作的复杂度降低到 $O(1)$ 的话，另一个操作势必会变为 $O(n)$ 。所以我们的目的还是要平衡复杂度。考虑在每个节点维护两个数据结构。数据结构的下标表示离 $u$ 为 $dis(u,v)$ 的权值之和。那么 $t_1$ 维护子树的权值和， $t_2$ 维护父亲的子树权值和。

那么查询答案的维护就可以转化为。每次从 $last$ 跳一下父亲 $now$ ，记录 $d=dis(now,x)$ ， $ans$ 加上 $t_1(now)$ 的 $k - d$ 的前缀和，再减去 $t_2(last)$ 中 $k- d$ 的前缀和。这个可以想做一个容斥，因为这一部分的答案已经在 $t_1(last)$ 中更新过了。
修改一个点的权值可以转化为。每次从 $last$ 跳父亲 $now$ ，记录 $d = dis(last,x)$ 。那么每次修改 $t_1(last)$ 的 $dis(x,last)$ 和 $t_2(last)$ 的 $dis(now,x)$ 的值就可以了。

有趣的发现，这个如果是随机数据的话就过了。因为随机数据下的树高为 $\log n$ 的。我们考虑一下其实这些操作已经与树原本的结构无关了。需要的东西也只有 $dis(v,u)$ 了。那么我们能不能考虑重构一棵树，使他的树高为 $\log n$ 呢。

重构树

其实就是固定一次点分的过程。我们知道，如果一个树按照重心来重新划分子树，那么最后的树高为 $\log n$ 。这里用图例解释一下样例。利用点分的思想。由于每走一次父亲，自己的在重构树上的 $size$ 至少要 $\times 2$ 。所以总的树高就是 $\log$ 了，保证了暴力跳父亲的复杂度。
图片说明

例题代码

\*
这题的大概步骤。
1 先进行一次dfs求出深度，原树上的父亲。这里采用了倍增lca，所以还要记录 2^k 级的父亲。
2 开始重构树，大概和淀粉质的过程类似，其中记录重构后的父亲 dfa 和大小 dsiz 两个数组。
3 每个节点维护一个动态开点的线段树，线段树上的下标表示距离，t1 维护自己的子树，t2 维护自己父亲在自己子树中元素。
4 初始化+查询+修改。修改每次修改的是原来和现在的增量。
*\
#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x :x ;
}
const int N = 5e5 + 190,inf = 0x3f3f3f3f;
struct Edge {int to,nxt;}e[N];
int head[N],ecnt,n,fa[N][22],dep[N],Log[N];
void addedge(int x,int y) {e[++ecnt] = {y,head[x]};head[x] = ecnt;}
int lca(int a,int b) {
    if(dep[a] < dep[b]) swap(a,b);int k = dep[a] - dep[b];
    for(int i = Log[k];~i;i--) if((k >> i) & 1) a = fa[a][i];
    if(a == b) return a;
    for(int i = Log[dep[a]];~i;i--) if(fa[a][i] ^ fa[b][i])
    a = fa[a][i],b = fa[b][i];return fa[a][0];
} //倍增lca
void dfs(int x,int F,int Dep) {
    dep[x] = Dep;fa[x][0] = F;
    for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == F) continue;
        dfs(y,x,Dep + 1);
    }
} // 第一次dfs，求深度
int distree(int a,int b) {return dep[a] + dep[b] - 2 * dep[lca(a,b)];} 
// 树上距离的公式
int root,size[N],maxs[N],vis[N];
int dsiz[N],dfa[N];
void getrt(int x,int F,int Tot) {
    size[x] = 1;maxs[x] = 0;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(vis[y] || y == F) continue;
        getrt(y,x,Tot);size[x] += size[y];
        maxs[x] = max(maxs[x],size[y]);
    }
    maxs[x] = max(maxs[x],Tot - size[x]);
    if(maxs[x] < maxs[root]) root = x;
} // 找出子树的重心，Tot 是这个子树的总大小
void rebuild(int x,int tots) {
    vis[x] = 1;dsiz[x] = tots;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(vis[y]) continue;
        int Tot = (size[y] < size[x]) ? size[y] : (tots - size[x]);
        maxs[root = 0] = inf;        
        getrt(y,x,Tot);dfa[root] = x;
        rebuild(root,Tot);
    }
} // 重构树，类别淀粉质的 solve 过程。
int rt1[N],rt2[N];
int Val[N];
struct Segmenttree {
    int lc[N << 3],rc[N << 3],sum[N << 3],size;
    void update(int &u,int pos,int k,int l,int r) {
        if(!u) u = ++size;sum[u] += k;
        if(l == r) return ;
        int mid = l + r >> 1;
        if(pos <= mid) update(lc[u],pos,k,l,mid);
        else update(rc[u],pos,k,mid + 1,r);
    }
    int query(int u,int L,int R,int l,int r) {
        if(L <= l && r <= R) return sum[u];
        if(l > R || r < L || !u) return 0;
        int mid = l + r >> 1;
        return query(lc[u],L,R,l,mid)+query(rc[u],L,R,mid + 1,r);
    } // 支持查询区间和和修改单点的动态开点线段树。
}t1,t2;
void update(int x,int val) {
    int now = x;
    while(now) {
        int F = dfa[now];
        t1.update(rt1[now],distree(now,x),val,0,dsiz[now]);
   if(F)t2.update(rt2[now],distree(F,x),val,0,dsiz[F]);
        now = F;
    } // 上文所述的跳父亲。
}
int query(int x,int k) {
    int res = 0;
    int now = x,last = 0;
    while(now) {
        int d = distree(x,now);
        if(d > k) {last = now;now = dfa[now];continue;}
        res += t1.query(rt1[now],0,k - d,0,dsiz[now]);
if(last)res -= t2.query(rt2[last],0,k - d,0,dsiz[now]);
        last = now;now = dfa[now];
    }
    return res;
}
int main() {
    n = read();int Q = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i <= n;i++) Val[i] = read();
    for(int i = 1,x,y;i < n;i++) {
        x = read();y = read();
        addedge(x,y);addedge(y,x);
    }
    dfs(1,0,1);maxs[root = 0] = inf;
    getrt(1,0,n);rebuild(root,n);
    for(int i = 1;i <= n;i++) update(i,Val[i]);
    int lastans = 0;
    while(Q--) {
        int opt = read(),x = read(),k = read();
        x ^= lastans;k ^= lastans;
        if(opt == 0) {
            lastans = query(x,k);
            printf("%d\n",lastans);
        }else {
            update(x,k - Val[x]);Val[x] = k;
        }
    }
    return 0;
}