【学习记录】点分治

点分治之前就学过，最近机房有人让我帮调，曹神又给了道好题，自己又学了点分树，因此简单记录一下。

点分治即每次找到树的重心，并以其为中心分治，处理跨过中心的所有路径，再递归下去处理不经过中心的子树内路径。处理方式为枚举其子树，先处理该子树与之前子树之间的路径，再将该子树内的点记录下来以便之后查询。由于以重心为根时，其子树大小不超过 $\frac{siz}2$，因此每个节点只会被处理 $O(\log n)$ 次，总复杂度为 $O(n\log n)$。思想大概就是这样，下面是例题。

### P3806 【模板】点分治 1

#### 题意

给定一棵树，边有边权，$q$ 次询问树上是否存在长为 $k$ 的路径，$n\le10^4,q\le 100,k\le 10^7$。

#### 题解

板题，直接点分治，开桶记录目前是否存在与分治中心距离为 $i$ 的路径，每次处理时枚举所有询问更新答案。需要注意处理完某个中心后不能清空整个桶，而是只单点清空所用到的，具体做法为另开数组记录所有 $d$，最后遍历该数组清空，这也是大部分点分治题保证复杂度的关键。时间复杂度 $O(qn\log n)$，空间复杂度 $O(n+k)$。

### 25.02-MX-D1T2 毒药

#### 题意

给定一棵树，点有点权 $a_i$，求满足 $a_x\oplus a_y\le \bigoplus_{i\in Path(x,y)} a_i$ 的二元组 $(x,y)$ 个数。$n\le2\times 10^5,a_i\le 2^{60}$。

#### 题解

记 $d_i$ 表示 $i$ 到根的路径异或和，则原条件转化为 $a_x\oplus a_y\le d_x\oplus d_y\oplus a_{LCA(x,y)}$。则容易想到枚举 LCA，统计不同子树之间点对的贡献。然而这样遍历的总次数没有保证，所以使用点分治，上式中 $d$ 也变成点到分治中心的路径异或和。则问题转化为动态维护集合 $S$，集合元素为 $(a,d)$ 二元组，多次询问 $(a_x,d_x)$，查询集合 $S$ 中有多少 $(a_y,d_y)$ 满足 $a_x\oplus a_y\le d_x\oplus d_y\oplus a_{rt}$。

发现只有令含 $x$ 项和含 $y$ 项分别在同侧，才能快速维护数量。但小于号没有交换律，所以先变不等号并移项，得到 $a_x\oplus d_x\oplus a_{rt}\ne a_y\oplus d_y$，然后按照 $a\oplus d$ 分类后枚举 LCP 长度，分讨不同的最高位，最后加上相等的贡献即可。实现只需开一棵以 $a\oplus d$ 为键值的 Trie 树，每个点记录子树内 $a$ 该位为 $0$ 或 $1$ 的个数，可通过 $a\oplus d$ 的情况得到 $d$ 该位的值。查询时从根到对应叶子遍历一条链，处理链上节点的兄弟节点即可。

本题点分治部分仅有基本应用，在计算贡献时用到了 Trie 树，这里清空只需要清掉开的所有点即可。可能没有提交通道，只有计算贡献部分的原题 [P7502](https://www.luogu.com.cn/problem/P7502)，之后有时间可能会造造数据。

### P10421 [蓝桥杯 2023 国 A] 树上的路径

#### 题意

给定一棵树，求树上所有长度在 $[L,R]$ 内的路径长度和，长度为边数。$n\le 10^6$。

#### 题解

先点分治，考虑如何统计路径长度和。若枚举到 $i$ 点，则之前子树内的 $j$ 需满足 $d_i+d_j\in [L,R]$，才能产生 $d_i+d_j$ 的贡献。即答案要加上 $\sum[L-d_i\le d_j\le R-d_i](d_j+d_i)$，拆括号后只需要求区间内个数和 $d_j$ 的和，开两棵树状数组即可实现，时间复杂度 $O(n\log^2 n)$。

但还是不够优秀，考虑求贡献时的实质，其实是钦定顺序为 $p_j<p_i$，在 $i$ 处计算贡献，其中 $p_x$ 表示 $x$ 所在的分治中心子树。因此若先把所有子树的贡献统计下来，并从中剔除当前子树的贡献来计算，就可以降低复杂度。对于本题，可以先将所有 $d_x$ 放入桶中并做前缀和，枚举某棵子树时对内部所有 $d_x$ 同样处理，求值时区间查询后用总值减去子树内的值即可。

问题在于对桶做前缀和需要值域大小的复杂度，然而某子树内的 $d$ 不会超过子树大小，因此总值需要的数组大小为 $siz_u$，单个子树内需要的数组大小为 $siz_v$，分析得总时间复杂度为 $O(n\log n)$，实际运行时由于有一定常数，且上个做法中的树状数组常数较小，优化后所用时间大概是上个做法的一半。优化后求贡献的代码片段：

~~~cpp
struct nod
{
	ll s[N]; int len;
	void cle(int x)
	{
		len=x;
		for(int i=0;i<=len;i++) s[i]=0;
	}
	void add(int p,ll x) {s[p]+=x;}
	void build() {for(int i=1;i<=len;i++) s[i]+=s[i-1];}
	ll qry(int p) {return s[min(p,len)];}
}Ta[2],Tb[2];
void sol(int u)
{
	d[u]=0,Ta[0].cle(siz[u]),Tb[0].cle(siz[u]),Ta[0].add(0,2);
	for(int v:e[u]) if(!vis[v])
	{
		tt=0,dfs(v,u);
		for(int i=1;i<=tt;i++) Ta[0].add(td[i],1),Tb[0].add(td[i],td[i]);
	}
	Ta[0].build(),Tb[0].build();
	for(int v:e[u]) if(!vis[v])
	{
		tt=0,dfs(v,u),Ta[1].cle(siz[v]),Tb[1].cle(siz[v]);
		for(int i=1;i<=tt;i++) Ta[1].add(td[i],1),Tb[1].add(td[i],td[i]);
		Ta[1].build(),Tb[1].build();
		for(int i=1;i<=tt;i++)
		{
			int l=max(0,L-td[i]),r=R-td[i];
			if(l>r) continue;
			ll x=Ta[0].qry(r)-Ta[1].qry(r),y=Tb[0].qry(r)-Tb[1].qry(r);
			if(l) x-=(Ta[0].qry(l-1)-Ta[1].qry(l-1)),y-=(Tb[0].qry(l-1)-Tb[1].qry(l-1));
			res+=x*td[i]+y;
		}
	}
}
~~~

### CF2101E Kia Bakes a Cake

#### 题意

给定一棵 $n$ 个点的树和长为 $n$ 的 $01$ 串 $s$。称长为 $m$ 的序列 $a$ 合法，当且仅当 $a$ 中元素两两不同，$\forall i\in[1,m],a_i\in[1,n],s_{a_i}=1$，且 $\forall i\in [1,m-2],2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2})$，其中 $d(u,v)$ 表示树上 $u,v$ 间简单路径的边数。对于 $x\in[1,n]$ 分别求 $a_1=x$ 时，合法 $a$ 序列的最大长度。$n\le 7\times 10^4$。

#### 题解

首先看到 $2d(a_i,a_{i+1})\le d(a_{i+1},a_{i+2})$ 可以很自然地注意到每次路径长度至少翻倍，而路径长度不会超过 $n-1$，因此序列长度不会超过 $O(\log n)$，或许会对本题有帮助。

之后考虑使用 DP 解决该问题，注意到 DP 状态中只能记录开头或结尾元素，难以限制两两不同。然而仔细考虑 $d$ 的限制后发现，若两次经过点 $x$，设第二个 $x$ 的前缀为 $y$，则有 $d(y,x)>d(x,p_1)+d(p_1,p_2)+\cdots+d(p_k,y)$，然而 $d(y,x)$ 是 $y\to x$ 的唯一最短路径，不可能存在比其长度更短的，因此序列合法时不可能存在相同元素，故可以忽略该限制。

因此 DP 就是可行的了，最朴素的 DP 状态为 $f_{x,i,j}$ 表示 $a_1=x$，结尾为 $i$ 且最后一条路径长度为 $j$ 的最长合法序列长度。然而容易想到 $x$ 这一维并不必要，可以将最终的序列倒过来考虑，设 $f_{i,j}$ 表示开头为 $i$，第一条路径长度为 $j$ 的最长合法序列长度，通过在开头加元素来转移，状态数压缩到了 $O(n^2)$，但还是难以接受。

这时想起答案不会超过 $O(\log n)$，因此 DP 值不会超过 $O(\log n)$。考虑将 DP 值和状态互换，显然序列长度相同时第一条路径越长越优。因此设 $f_{i,x}$ 表示开头为 $i$，长为 $x$ 的合法序列中第一条路径的最大长度，这样状态数就变成 $O(n\log n)$ 的了。

之后考虑转移，$f_{j,x+1}\leftarrow d(i,j)$ 需要满足 $2d(i,j)\le f_{i,x}$。考虑枚举 $x$ 进行 $O(\log n)$ 轮转移，并使用点分治优化，即在分治中心处转移所有路径经过中心的 $(i,j)$ 对。则 $i$ 转移到 $j$ 的值为 $d_i+d_j$，有限制 $2(d_i+d_j)\le f_{i,x}$，拆开得到 $2d_i-f_{i,x}\le -2d_j$，这里 $d_x$ 为深度。因此以 $2d-f$ 为下标，用树状数组记录前缀 $d_i$ 的最大值即可进行转移。这里需要在点分治处理时正反跑两遍，总时间复杂度 $O(n\log^3 n)$，分别来自状态数、点分治和树状数组，在 6s 的时限下已经可以通过，[代码](https://codeforces.com/contest/2101/submission/319606177)。

考虑能否优化到 $O(n\log^2n)$，发现正反跑两遍的过程实际上是把 $p_i\ne p_j$ 的限制拆成了 $p_i<p_j$ 或 $p_i>p_j$，其中 $p_x$ 表示 $x$ 所在的分治中心子树。如果能将所有子树的信息预处理到一起，查询时快速去掉 $p_j$ 子树内的信息并转移，就能降低复杂度。考虑把上式整个取反为 $f_{i,x}-2d_i\ge 2d_j$，在每个下标上维护 $d$ 的最大值和所属子树不同的次大值，并预处理出后缀信息。由于最大值和次大值信息合并可以 $O(1)$ 实现，整个后缀处理仍是线性的，查询时取子树外的最大值即可。

注意到查询的 $d_j$ 不会超过 $siz_u$，因此把超过 $2siz_u$ 的下标上的值均赋到 $2siz_u$ 上即可，数组大小得到保证，总时间复杂度 $O(n\log^2n)$，[代码](https://codeforces.com/contest/2101/submission/319610589)。由于常数较大，实际并没有比原来快多少。事实上限制式可以整体除以 $2$，得到 $\lfloor \frac{f_{i,x}-2d_i}2\rfloor\ge d_j$，可以通过数组大小少个 $2$ 的常数，然而[也没快多少](https://codeforces.com/contest/2101/submission/319612293)，可能是实现得比较粗糙了。

### P6329 【模板】点分树 | 震波

#### 题意

给定一棵树，点有点权，需要支持单点修改，查询距某点不超过 $k$ 的点权和，两点间距离为边数。强制在线，$n,q\le 10^5$。

#### 题解

点分树是点分治的应用之一。具体地，令分治中心以上一层分治中心为父亲，建出一棵点分树。与点分治类似，点分树的深度不会超过 $O(\log n)$，同时所有点的子树大小之和也是 $O(n\log n)$ 级别的。这允许我们暴力枚举某个点到根路径上的所有点，也允许对每个点记录其子树内所有点的信息。

这时对于某两点 $u,v$ 间的路径，我们用点分树上 LCA 代替原树 LCA 作为分界点，这样对于固定点 $u$，不同的分界点 $x$ 只有 $dep(u)$ 个，可以枚举。这时与 $u$ 以 $x$ 为 LCA 的节点为 $x$ 子树中除去 $s$ 子树的部分，$s$ 为 $x$ 子节点中子树内包含 $u$ 的。因此对每个点 $x$，分别记录其子树内与 $x$ 和 $x$ 父亲间路径的情况，查询时枚举 $x$，并用 $x$ 和 $s$ 的信息处理出有效信息即可。

对于本题，有 $dis_{u,v}=dis_{u,x}+dis_{x,v}$，枚举 $x$ 后要查询 $dis_{x,v}\le k-dis_{u,x}$ 的点权和。因此在每个点上要分别记录其子树内的点与其和其父亲距离为 $d$ 的点权和，求贡献时用 $x$ 对应区间的和减去 $s$ 对应区间的和即可。因此使用 $2n$ 棵动态开点线段树分别维护区间和，修改时对其到根路径上的所有点均修改即可。

时间复杂度为 $O((n+q)\log^2n)$，用 $O(1)$ LCA 求距离可去掉一个 log；空间复杂度理论上是 $O(n\log^2 n)$ 的，因为线段树的有效下标总数为 $O(n\log n)$，然而这里远远不满，用 vector 动态开点可以通过。主函数代码：

~~~ cpp
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,mx[0]=n,T[0].build(n),T[1].build(n);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++)
	{
		int u,v; cin>>u>>v;
		e[u].pb(v),e[v].pb(u);
	}
	tot=n,getrt(1,0),ra=rt,getrt(rt,0),solv(rt),dfs0(1,0),dfs1(1,1),dfs2(ra);
	for(int u=1;u<=n;u++) for(int i=id[u];i<id[u]+s[u];i++)
	{
		int v=p[i]; T[0].update(u,0,n,dis(v,u),a[v]);
		if(f[u]) T[1].update(u,0,n,dis(v,f[u]),a[v]);
	}
	while(m--)
	{
		int op,x,y; cin>>op>>x>>y,x^=last,y^=last;
		if(op)
		{
			int u=x,dt=y-a[x]; a[x]=y;
			while(u)
			{
				if(f[u]) T[1].update(u,0,n,dis(x,f[u]),dt);
				T[0].update(u,0,n,dis(x,u),dt),u=f[u];
			}
		}
		else
		{
			int u=x,lp=x; last=0;
			while(u)
			{
				int d=y-dis(u,x);
				if(d>=0)
				{
					last+=T[0].query(u,0,n,0,d);
					if(u!=x) last-=T[1].query(lp,0,n,0,d);
				}
				lp=u,u=f[u];
			}
			cout<<last<<'\n';
		}
	}
	return 0;
}
~~~

正在渲染内容...