#C241030A. 点分树

标签（Label）

点分树
动态开点线段树
LCA
动态规划
容斥原理
模板

网址（Website）

P6329 【模板】点分树 | 震波 - 洛谷

【NOIP模版】点分树 - 震波 - Super

题目（Problem）

题目描述

在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value_i$。

不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。

接下来你需要在线处理 $m$ 次操作：

0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。

1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。

为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。

输入格式

第一行包含两个正整数 $n$ 和 $m$ 。

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。

接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。

接下来 $m$ 行，每行包含三个数，表示 $m$ 次操作。

输出格式

包含若干行，对于每个询问输出一行一个正整数表示答案。

样例 #1

样例输入 #1

8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1

样例输出 #1

11100101

提示

数据规模与约定

对于 $100 %$ 的数据，有 $1\leq n,m\leq 10^5, 1\leq u,v,x\leq n, 1\leq value_i,y\leq 10^4,0\leq k\leq n-1$ 。

upd：样例范围与题目真实数据范围不同，以提示中给出的数据范围为准。

说明

题目来源：BZOJ3730。

题解（Solution）

到处都是题解，我就不讲太复杂，把自己没搞懂的地方搞懂就好。

点分树有以下性质：

所有的子树大小之和为 $O(n\log n)$ 。
点分树的树高为 $O(\log n)$
任意两点在点分树上的 $\text{LCA}$ 一定在原树中这两个点的路径上。

考虑如何利用这些性质来做这道题。设 $f_{x,k}$ 表示 $x$ 的子树中到 $x$ 距离 $\le k$ 的点的权值和，建出点分树后，我们对每个点在点分树上暴力跳祖先更新贡献（可以在原树上维护 $\text{LCA}$ 来计算距离），对于每个点记录一个值域线段树，并且在对应位置上更新权值，为节省空间，可以使用动态开点线段树（类似可持久化线段树的做法），由于每个点最多纪录 $O(\log n)$ 次贡献，所以总空间复杂度为 $O(n\log n)$ ，最后计算答案的时候可以在点分树上暴力往上跳距离，对于祖先 $i$ 每次查询 $\le k-dis(x,i)$ 的点的贡献，为防止算重，还要减去祖先 $i$ 在 $x$ 方向上的子树的贡献，总时间复杂度 $O(n\log^2n)$ 。

为防止卡常，请使用 $O(1)$ 求 $\mathrm{LCA}$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 101234;
const int B = 17;
bool ST;

vector<int> ft[N];
int n,q,ans,a[N];

struct LCA{
	int f[N][24],dfn[N],idx;
	int dep[N];
	void dfs(int x,int F){
		f[dfn[x]=++idx][0] = F, dep[x] = dep[F]+1;
		for(int y:ft[x]) if(y^F) dfs(y,x);
	}
	inline int cmn(int x,int y){return dfn[x]<dfn[y]?x:y;}
	inline int lca(int x,int y){
		if(x==y) return x;
		if((x=dfn[x])>(y=dfn[y])) swap(x,y);
		int d = __lg(y-x++);
		return cmn(f[x][d], f[y-(1<<d)+1][d]);
	}inline int dis(int x,int y){return dep[x]+dep[y]-2*dep[lca(x,y)];}
	void init(){
		dfs(1,0);
		For(j,1,B) for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j] = cmn(f[i][j-1], f[i+(1<<(j-1))][j-1]);
	}
}G;

#define mid ((l+r)>>1)
#define ls tr[p].l
#define rs tr[p].r 
struct Segment_Tree{
	struct Tr{int l,r,v;}tr[N*32];int rt[N],idx;
	void pushup(Tr &T,Tr L,Tr R){T.v=L.v+R.v;}
	void update(int &p,int l,int r,int k,int v){
		if(!p) p = ++idx;
		if(l==r) return tr[p].v += v, void();
		if(k<=mid) update(ls,l,mid,k,v);
		else update(rs,mid+1,r,k,v);
		pushup(tr[p],tr[ls],tr[rs]);
	}
	int ask(int p,int l,int r,int L,int R){
		if(!p) return 0;
		if(L<=l && r<=R) return tr[p].v;
		if(R<=mid) return ask(ls,l,mid,L,R);
		if(L>mid) return ask(rs,mid+1,r,L,R);
		return ask(ls,l,mid,L,R) + ask(rs,mid+1,r,L,R);
	}
}T1,T2;
#undef mid
#undef ls 
#undef rs

struct Point_Tree{
	int siz[N], rt, mx;
	bitset<N> vst;
	int fa[N];
	void dfs_root(int x,int F,int sum){
		int sub = 0;siz[x] = 1;
		for(auto y:ft[x]) if(y^F && !vst[y])
			dfs_root(y,x,sum), siz[x]+=siz[y], sub=max(sub,siz[y]);
		sub = max(sub, sum-siz[x]);
		if(sub < mx) rt = x, mx = sub;
	}
	void devide(int x,int sum){
		vst[x] = true;
		for(auto y:ft[x]) if(!vst[y]){
			rt = 0, mx = N, siz[y] = siz[x]>siz[y]?siz[y]:sum-siz[x];
			dfs_root(y,x,siz[y]), fa[rt] = x, devide(rt, siz[y]);
		} 
	}
	void init(){rt = 0, mx = N, dfs_root(1,0,n), devide(rt, n);}
	void modify(int x,int v){
		for(int i=x;i;i=fa[i]){
			T1.update(T1.rt[i],0,n-1,G.dis(x,i),v);
			if(fa[i]) T2.update(T2.rt[i],0,n-1,G.dis(x,fa[i]),v);
		}
	}	
	int ask(int x,int k){
		int res = 0;
		for(int i=x,j=0;i;j=i,i=fa[i]){
			if(G.dis(x,i) > k) continue;
			res += T1.ask(T1.rt[i],0,n-1,0,k-G.dis(x,i));
			if(j) res -= T2.ask(T2.rt[j],0,n-1,0,k-G.dis(x,i));
		}return res;
	}
}T;


void Solve(){
	n=rd(),q=rd();For(i,1,n) a[i]=rd();
	For(i,1,n-1){
		int x=rd(), y=rd();
		ft[x].push_back(y);
		ft[y].push_back(x);
	}G.init(), T.init();
	For(i,1,n) T.modify(i,a[i]);
	while(q--){
		int opt=rd(),x=rd()^ans,y=rd()^ans;
		if(!opt) printf("%d\n", ans=T.ask(x,y));
		else T.modify(x,y-a[x]), a[x] = y;
	}
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}