点分树
给出n个节点的树，树上节点有点权$w_i$
进行q次强制在线操作：
- 操作0: 查询距离节点x距离小于等于y的所有节点的点权和
- 操作1: 将节点x的值修改为y
该题主要关心节点之间的距离，所以一定程度上与树本身的拓扑结构无关，因而考虑将原树重构为结构优秀的点分树，该树的高度不超过$logn$。重构后对每个点开桶，tong[i]记录该节点所有与之距离为i的孩子的点权和。因为点分树结构优秀，所以空间消耗仅为$O(nlogn)$。
这样，类似于点分治，对某个节点x的查询就相当于分治地查询x的所有祖先作出的贡献。
但同样类似于点分治，对某节点u的父亲par[u]进行统计时，有可能会出现和节点u贡献重复的部分，因而对父亲节点进行统计前应该将当前节点可能算重的贡献减去，这样才能不重复地计算点权和。而由于点分树完全破坏了原树的拓扑结构，因而仅仅知道u节点所有孩子对u的贡献(即上述的tong)是不能够通过距离+1等简单的手段知道u节点所有孩子对par[u]的贡献的，所以对每个节点我们应该开两个桶，一个记录对自身的贡献，一个记录对父亲的贡献。而该题要求能单点修改桶中权值，区间查询桶的前缀和，因而该桶至少应该是bit，而由于本人太菜不擅长bit，就使用动态开点的线段树完成动态的修改、查询。当修改时，不断向上爬，根据距离不断地修改两棵线段树；当查询时，不断地向上爬，去除重复的部分，求和统计。
此外，为了快速求原树中两点的距离，我们花费$O(nlogn)$的时间、空间在dfn序上建立st表，$O(1)$地完成每次的查询。
总体时间复杂度大概是$O(nlog^2n)$
树套树难写的一比，春节前写到自闭，昨天晚上重新写写到半夜总算过了。
码力实在太挫了
有一些坑点放在template里进行注解。
1#define mid ((l + r) >> 1)
2
3const int manx = 1e5 + 10;
4//根据dfn数组的长度决定N(即N = log2(cnt), cnt = maxn << 1)
5const int N = 20;
6const double eps = 1e-6;
7
8int n, q;
9int w[manx];
10//动态开点的单点修改、区间求和线段树
11//维护两个st，一个是u子树对u的贡献，另一个是u子树对par[u]的贡献（如果有的话）
12const int M = maxn * N * 4;
13struct SEG{
14 int root[maxn];
15 int st[M], ls[M], rs[M], top = 0;
16 int build(int l, int r){
17 int now = top++;
18 if(l == r) return now;
19 ls[now] = build(l, mid);
20 rs[now] = build(mid + 1, r);
21 return now;
22 }
23 void up(int p){st[p] = st[ls[p]] + st[rs[p]];}
24 void add(int p, int l, int r, int k, int x){
25 assert(k >= l && k <= r);
26 if(l == r && l == k){
27 st[p] += x;
28 return ;
29 }
30 if(k <= mid) add(ls[p], l, mid, k, x);
31 else add(rs[p], mid + 1, r, k, x);
32 up(p);
33 }
34
35 int query(int p, int l, int r, int L, int R){
36 if(R < L) return 0;
37 if(L <= l && r <= R) return st[p];
38 int ans = 0;
39 if(L <= mid) ans += query(ls[p], l, mid, L, R);
40 if(R > mid) ans += query(rs[p], mid + 1, r, L, R);
41 return ans;
42 }
43}seg[2];
44
45
46vector<pair<int, int>> E;
47struct TREE{
48 int head[maxn], par[manx], top = 0;
49 struct star{int to, next;};
50 star edge[maxn << 1];
51
52 TREE(){clr(head, -1); top = 0;}
53
54 void add(int u, int v){
55 edge[top].to = v;
56 edge[top].next = head[u];
57 head[u] = top++;
58 }
59 void add(vector<pair<int, int>> &E){
60 for(auto e: E){
61 add(e.first, e.second);
62 par[e.second] = e.first;
63 }
64 }
65
66 int mx[maxn], sze[maxn], vis[maxn], root = 0, S;
67 void getroot(int now, int par){
68 sze[now] = 1; mx[now] = 0;
69 for(int i = head[now]; ~i; i = edge[i].next){
70 int to = edge[i].to; if(to == par || vis[to]) continue;
71 getroot(to, now);
72 sze[now] += sze[to];
73 mx[now] = max(mx[now], sze[to]);
74 }
75 mx[now] = max(mx[now], S - sze[now]);
76 if(mx[root] > mx[now]) root = now;
77 }
78 //当前分治中心为now，封锁住通往par的路径，函数返回重心
79 int divide(int now, int par){
80 root = 0; getroot(now, par);
81 int rt = root; vis[rt] = 1;
82 for(int i = head[rt]; ~i; i = edge[i].next){
83 int to = edge[i].to; if(to == par || vis[to]) continue;
84 S = sze[to];
85 E.push_back({rt, divide(to, rt)});
86 }
87 return rt;
88 }
89 //将树重构为点分树，点分数的边存放在E中，供tree[1].add调用；返回重构树的根
90 int rebuild(){
91 S = mx[0] = n;
92 return divide(1, 0);
93 }
94
95 //初始化dfn、pos数组，得到每个节点的深度dep
96 int dfn[maxn << 1], pos[manx], cnt = 0;
97 int dep[maxn];
98 void dfs(int now, int par){
99 dfn[cnt] = now; pos[now] = cnt; cnt++;
100 for(int i = head[now]; ~i; i = edge[i].next){
101 int to = edge[i].to; if(to == par) continue;
102 dep[to] = dep[now] + 1;
103 dfs(to, now);
104 dfn[cnt++] = now;
105 }
106 }
107
108 int st[maxn << 1][N];
109 //通过深度数组获取st表, st维护区间中深度最小的节点标号
110 void getst(){
111 dfs(1, 0);
112 for(int i = 0; i < cnt; i++) st[i][0] = dfn[i];
113 for(int j = 1; j < N; j++){
114 for(int i = 0; i < cnt; i++){
115 int nxt = i + (1 << (j - 1));
116 if(nxt >= cnt) st[i][j] = st[i][j - 1];
117 else if(dep[st[i][j - 1]] < dep[st[nxt][j - 1]]) st[i][j] = st[i][j - 1];
118 else st[i][j] = st[nxt][j - 1];
119 }
120 }
121 }
122 //O1获取两点之间的距离
123 int getdis(int x, int y){
124 if(x == y) return 0;
125 int l = min(pos[x], pos[y]), r = max(pos[x], pos[y]);
126 int k = (int)(log2(r - l) + eps);
127 int lca = st[l][k];
128 if(dep[lca] > dep[st[r - (1 << k) + 1][k]]) lca = st[r - (1 << k) + 1][k];
129 return dep[x] + dep[y] - 2 * dep[lca];
130 }
131 //获取子树大小并初始化线段树
132 void ini(int now, int par){
133 sze[now] = 1;
134 for(int i = head[now]; ~i; i = edge[i].next){
135 int to = edge[i].to; if(to == par) continue;
136 ini(to, now);
137 sze[now] += sze[to];
138 }
139 seg[0].root[now] = seg[0].build(0, sze[now]);
140 seg[1].root[now] = seg[1].build(0, sze[now] + 1);
141 }
142}tree[2];
143
144
145//第k个城市上发生x的增量，当前处理到now节点，保证now节点一定是k的祖先
146void add(int now, int k, int x){
147 int dis = tree[0].getdis(now, k);
148 seg[0].add(seg[0].root[now], 0, tree[1].sze[now], dis, x);
149 if(tree[1].par[now]){
150 dis = tree[0].getdis(tree[1].par[now], k);
151 seg[1].add(seg[1].root[now], 0, tree[1].sze[now] + 1, dis, x);
152 add(tree[1].par[now], k, x);
153 }
154}
155
156//查询距离k城市距离小于等于x的价值和，当前处理到now
157int query(int now, int k, int x){
158 int ans = 0;
159 int d = tree[0].getdis(now, k);
160 ans += seg[0].query(seg[0].root[now], 0, tree[1].sze[now], 0, x - d);
161 if(tree[1].par[now]){
162 int D = tree[0].getdis(tree[1].par[now], k);
163 ans -= seg[1].query(seg[1].root[now], 0, tree[1].sze[now] + 1, 0, x - D);
164 ans += query(tree[1].par[now], k, x);
165 }
166 return ans;
167}
168
169
170int main(){
171// Fastin;
172 scanf("%d %d", &n, &q);
173 for(int i = 1; i <= n; i++) scanf("%d", w + i);
174 for(int i = 0; i < n - 1; i++){
175 int u, v; scnaf("%d %d", &u, &v);
176 tree[0].add(u, v); tree[0].add(v, u);
177 }
178
179 tree[0].getst();
180
181 int root = tree[0].rebuild();
182 tree[1].add(E);
183
184 tree[1].ini(root, 0);
185
186 for(int i = 1; i <= n; i++) add(i, i, w[i]);
187
188 int ans = 0;
189 whlie(q--){
190 int op, x, y; scanf("%d %d %d", &op, &x, &y);
191 x ^= ans; y ^= ans;
192 if(op){
193 add(x, x, y - w[x]);
194 w[x] = y;
195 }
196 else printf("%d\n", ans = query(x, x, y));
197 }
198
199 return 0;
200}