终于写了点分树，iee
题目描述：给定一棵点带权的树，在线维护两种操作：(1) 查询距离点 (x) 不超过 (y) 的所有点的权值和 (2) 单点修改。
数据范围：(n,mle 10^5)，权值范围是 ([1,10^4])，洛谷时限 2s。
首先点分治可以用来解决路径问题，因为 (u,v) 在点分树上的 lca 一定在原树路径上，同时保证了深度 (log n)
如果不带修的话，首先每个点维护一个 vector，下标为该点在点分树上的子树到该点的距离，值为距离不超过 (y) 的权值和。再维护一个“到该点父亲的距离”的 vector 用于去除重复贡献。
于是对于一次询问 (x)，枚举它在点分树上的祖先 (g)，考虑 (g) 为 lca 时的答案，那么在这个 vector 上查询距离不超过 (y-dis(x,g)) 即可，再刨去与 (x) 在同一个子树的贡献（因为此时 lca 就不是 (g) 了）
至于带修，把前缀和改成 BIT 即可，修改时候枚举祖先，把对应的下标上的值修改即可。时间复杂度 (O(nlog^2n))，空间复杂度 (O(nlog n))。
至于求距离，还是不要在点分树建树的时候预处理了，那样写得太麻烦，实现不好的话常数还很大。可以用 rmq 求 lca 的方法求距离，都是 (O(nlog n)-O(1)) 的复杂度还好写。
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 100004;
template<typename T>
inline void read(T &x){
int ch = getchar(); x = 0;
for(;ch < '0' || ch > '9';ch = getchar());
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
}
template<typename T>
inline bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
template<typename T>
inline bool chmin(T &a, const T &b){if(a > b) return a = b, 1; return 0;}
int n, m, head[N], to[N << 1], nxt[N << 1], val[N], lans, opt, x, y;
inline void add(int a, int b){
static int cnt = 0;
to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;
}
int dep[N], st[17][N << 1], dfn[N], tim, lg2[N << 1];
void dfs1(int x, int f = 0){
st[0][++ tim] = x; dfn[x] = tim;
for(Rint i = head[x];i;i = nxt[i]) if(to[i] != f){
dep[to[i]] = dep[x] + 1; dfs1(to[i], x);
st[0][++ tim] = x;
}
}
inline int LCA(int u, int v){
u = dfn[u]; v = dfn[v];
if(u > v) swap(u, v);
int k = lg2[v - u + 1], a = st[k][u], b = st[k][v - (1 << k) + 1];
return dep[a] < dep[b] ? a : b;
}
inline int dis(int u, int v){return dep[u] + dep[v] - (dep[LCA(u, v)] << 1);}
int siz[N], rt, wson[N], tot;
bool vis[N];
void dfs2(int x, int f = 0){
siz[x] = 1; wson[x] = 0;
for(Rint i = head[x];i;i = nxt[i]) if(to[i] != f && !vis[to[i]]){
dfs2(to[i], x); siz[x] += siz[to[i]]; chmax(wson[x], siz[to[i]]);
}
chmax(wson[x], tot - siz[x]);
if(wson[x] < wson[rt]) rt = x;
}
int fa[N], mxdep;
vector<int> tr1[N], tr2[N];
inline int EI(int x){return x & -x;}
void change(vector<int> &tr, int p, int v){int len = tr.size(); for(;p < len;p += EI(p)) tr[p] += v;}
int query(const vector<int> &tr, int p){int ans=0;chmin(p,(int)tr.size()-1);for(;p;p-=EI(p)) ans+=tr[p];return ans;}
void calc(int x, int rt, int len = 1, int f = 0){
siz[x] = 1;
for(Rint i = head[x];i;i = nxt[i])
if(to[i] != f && !vis[to[i]]){
calc(to[i], rt, len + 1, x);
siz[x] += siz[to[i]];
}
chmax(mxdep, len);
}
void calc2(int x, int rt, int len = 1, int f = 0){
change(tr1[rt], len, val[x]);
if(fa[rt]) change(tr2[rt], dis(fa[rt], x) + 1, val[x]);
for(Rint i = head[x];i;i = nxt[i]) if(to[i] != f && !vis[to[i]])
calc2(to[i], rt, len + 1, x);
}
void work(int x){
vis[x] = true; mxdep = 0;
calc(x, x); tr1[x].resize(mxdep + 1);
int tmp = mxdep; calc2(x, x);
for(Rint i = head[x];i;i = nxt[i]) if(!vis[to[i]]){
tot = siz[to[i]]; rt = 0; dfs2(to[i], x); fa[rt] = x; tr2[rt].resize(tmp + 1); work(rt);
}
}
int main(){
read(n); read(m);
for(Rint i = 1;i <= n;++ i) read(val[i]);
for(Rint i = 1, u, v;i < n;++ i){
read(u); read(v); add(u, v); add(v, u);
}
dfs1(1); lg2[0] = -1;
for(Rint i = 1;i <= tim;++ i) lg2[i] = lg2[i >> 1] + 1;
for(Rint k = 0;k < 16;++ k)
for(Rint i = 1;i <= tim - (1 << k + 1) + 1;++ i)
st[k + 1][i] = dep[st[k][i]] < dep[st[k][i + (1 << k)]] ? st[k][i] : st[k][i + (1 << k)];
wson[0] = 1e9; tot = n; dfs2(1); work(rt);
while(m --){
read(opt); read(x); read(y); x ^= lans; y ^= lans;
if(opt){
int del = y - val[x]; val[x] = y; change(tr1[x], 1, del);
for(Rint i = x;fa[i];i = fa[i]){
int tmp = 1 + dis(fa[i], x);
change(tr1[fa[i]], tmp, del);
change(tr2[i], tmp, del);
}
} else {
lans = query(tr1[x], y + 1);
for(Rint i = x;fa[i];i = fa[i]){
int tmp = y - dis(x, fa[i]) + 1;
if(tmp <= 0) continue;
lans += query(tr1[fa[i]], tmp) - query(tr2[i], tmp);
}
printf("%d
", lans);
}
}
}