说在前面的
我一看到是点分树,马上就点进来了,很快啊。前置知识:点分治。
- 约定
- 表示 的树上路径长度。
引入
给出一颗 个点的树,每个点有一个权值,有两种操作,一种是将某个点的权值修改为 ,另一种是查询距离点 不超过 的点的权值和。
分析
我们考虑暴力,如果将一个操作的复杂度降低到 的话,另一个操作势必会变为 。所以我们的目的还是要平衡复杂度。考虑在每个节点维护两个数据结构。数据结构的下标表示离 为 的权值之和。那么 维护子树的权值和, 维护父亲的子树权值和。
那么查询答案的维护就可以转化为。每次从 跳一下父亲 ,记录 , 加上 的 的前缀和,再减去 中 的前缀和。这个可以想做一个容斥,因为这一部分的答案已经在 中更新过了。
修改一个点的权值可以转化为。每次从 跳父亲 ,记录 。那么每次修改 的 和 的 的值就可以了。
有趣的发现,这个如果是随机数据的话就过了。因为随机数据下的树高为 的。我们考虑一下其实这些操作已经与树原本的结构无关了。需要的东西也只有 了。那么我们能不能考虑重构一棵树,使他的树高为 呢。
重构树
其实就是固定一次点分的过程。我们知道,如果一个树按照重心来重新划分子树,那么最后的树高为 。这里用图例解释一下样例。利用点分的思想。由于每走一次父亲,自己的在重构树上的 至少要 。所以总的树高就是 了,保证了暴力跳父亲的复杂度。
例题代码
\* 这题的大概步骤。 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; }
总结
- 大概就是重构树之后,由于树高是 的了,暴力跳父亲就对了。
- 时刻要注意我们是在虚树上跳父亲,虚树上的距离没有任何实际意义,更没有什么单调性。所以 时,任意要继续跳,而不是退出。
其它例题咕咕咕了