关于维护动态的树的直径
文章目录
单纯想记录一些动态维护树的直径的方法。
以下初始例题都是CF1192B Dynamic Diameter
- 欧拉序+线段树维护RMQ
可以用来解决一些树形态不变的问题。
线段树维护全$dfs$序 全$dfs$序为，仍然$dfs$遍历一棵树，每次访问到一个节点就把它记到序列末端 (下面称这时序列的长度为该的$bg$,序列称为$dfn$) 同时每当一个节点的子树的访问正式结束，也把它的父亲记到序列末端
考虑节点$u$,$v$不妨设$bg[u]<bg[v]$以及它们的LCA 显然$u$,$v$必然分属LCA的两个子树，于是在访问$v$之前,$u$所在子树的访问一定已经结束,所以LCA必定存在于$(bg[u],bg[v])$之间 显然，访问v时，对LCA子树访问不可能结束，于是$(bg[u],bg[v])$之间不可能有比LCA更浅的节点 LCA的深度是$[bg[u],bg[v]]$这一段区间里所有节点的深度的下界，而且它一定存在。所以它就是这段区间里的深度最小值，假设$u,v$两点在欧拉序的任意一个区间的两个端点是$l,r$，那么$dep[LCA(u,v)]=\min\limits_{l\leq k \leq r}{dep[dfn[k]] }$。
树上两点距离可以表示为$dis[u]+dis[v]-2\times dis[LCA(u,v)]$
考虑维护一条长为$2N-1$的序列$A[i]=dep[dfn[i]]$。所以求直径的问题可以转化为求 $$ \max\limits_{1\leq l\leq r\leq 2N-1}{A[l]+A[r]-2\times \min\limits_{l\leq k\leq r}{ A[k]} } $$
考虑使用线段树维护这个东西。
设 $$ Diameter[L,R]=\max\limits_{L\leq l\leq r\leq R} {A[l]+A[r]-2\times \min_{l\leq k\leq r}{A[k] } } $$ 直径为$Diameter[1,2N-1]$。
考虑固定$l$，式子将变为$(k,r)$两个变量。考虑维护区间内下式的值$(l\leq i,j\leq r)$ $$ rmx[l,r]=A[i]-2\times \min\limits_{i\leq j}{A[j]} $$
$$ lmx[l,r]=A[i]-2\times \min\limits_{j\leq i}{A[j]} $$
如果latex崩了就看图片吧(
令$m$为$(l,r)$中点，考虑$l,k,r$和$m$的关系，有 $$ \begin{equation}
Diameter[L,R]= \max
\left{\begin{array}{lr} Diameter[m+1,R] & , & (m<l\leq k\leq r) \
mx[L,m]+rmx[m+1,R] & , & (l\leq m<k\leq r) \ lmx[L,m]+mx[m+1,R] & , &(l\leq k\leq m< r) \ Diameter[L,m] & , &(l\leq k\leq r\leq m) \
\end{array}
\right.
\end{equation}
$$
同时$rmx$和$lmx$也可以使用这种思路求出
$$
\begin{equation}
rmx[L,R]=\max \left{\begin{array}{lr} rmx[m+1,R] & , & (m<l \leq r)\ mx[L,m]-2\times mn[m+1,R] & , &(l\leq m< r)\ rmx[L,m] & , &(l\leq r\leq m) \end{array} \right.
\end{equation}
$$
$$
\begin{equation}
lmx[L,R]=\max \left{\begin{array}{lr} lmx[L,m] & , &(l\leq r\leq m)\ mx[m+1,R]-2\times mn[L,m] & , &(l\leq m<r) \ lmx[m+1,R] & , &(m<l\leq r) \end{array} \right.
\end{equation}
$$
因为修改边权只对这条边深度较深一段的子树造成影响，而子树可以转化为欧拉序上的一段区间的修改。记录每个点对应的子树区间，也就是在欧拉序上的最早和最晚出现的位置，就可以将边权修改也转化为区间操作。只要记录这五个值和懒标记就可以维护这道题的信息了。
时间复杂度为$O(n\log n)$
|
|
- 树剖维护维护点集
考虑树上两个点集$S,T$
设$d(S)$表示$S$点集中距离最远的某两个点,$S\cup T$中必然存在两个点，使得其距离最远 且两端均在$d(S)\cup d(T)$中。也就是说在合并两个点集并直径时,只需要讨论$O(1)$种可能的直径 在dfs序上建一棵线段树。线段树的每个区间$[l,r]$，维护dfs序在$[l,r]$内这些点组成的点集的直径 一次修改只会修改$[beg[x],en[x]]$相交且不包含的区间，容易发现这样的区间只有$O(\log n)$个,暴力更新即可. 即所经过的所有非终点节点。
时间复杂度$O(n+q\log ^2)$
|
|
- LCT（还支持加边删边操作）
LCT的辅助树维护树内维护的是一条链，考虑维护这条实链上的最浅和最深的节点到当前子树内的最远距离。由于轻边实际上是父亲与这棵Splay上深度最小的点连的边，设$lmx[i]$表示$i$这棵Splay子树内深度最小的点往下的最大深度。当然因为Splay需要支持翻转操作，我们还需要维护这棵Splay上深度最大的点往下的最大深度rmx，当将Splay翻转过来时直接$swap(lmx,rmx)$即可。
接下来考虑lmx和rmx如何转移。以lmx的转移为例。
先考虑实链的转移
有 $$ lmx[x]=\max(lmx[x],lmx[son[x][0]]) $$ 即直接从原树的祖先转移下来。
以及 $$ lmx[x]=\max(lmx[x],lmx[son[x][1]]+sum[son[x][0]]+len[x]) $$ 即保留子树的答案再加上祖先和自身这条边的距离。
再考虑虚子树的转移。由于实链上深度最小的点实际上也是原树上子树的根节点。所以$lmx[x]$也可以表示为子树内深度最小的节点到子树内一点最远距离，那么有 $$ lmx[x]=\max(lmx[x],Chain.Fir+sum[son[x][0]]+len[x]) $$ 即从虚儿子中深度最大的节点转移即可，这可以使用一个可删堆或者multiset来维护。
rmx同理。
接下来考虑$mxd[i]$最长链的转移。
仍然先考虑实链的转移有 $$ mxd[x]=\max(mxd[x],rmx[son[x][0]]+lmx[son[x][1]]+len[x]) $$ 即祖先深度最大的点到子树深度最小的点以及自身这条边的距离。
以及 $$ mxd[x]=\max(mxd[x],mxd[son[x][0]],mxd[son[x][1]]) $$ 即祖先和子树本来就有的最长链
再考虑虚子树的转移
最长链有可能是虚子树中本来就有的一条最长链，这同样也可以使用可删堆或者multiset维护。 $$ mxd[x]=\max(mxd[x],Path.Fir) $$ 当然也有可能是两条虚子树的链和自身这条边拼起来的，所以还有： $$ mxd[x]=\max(mxd[x],Chain.Fir+Chain.Sec+len[x]) $$ 最后附上代码
|
|