长链剖分学习笔记

长链剖分是一种将树剖分成若干条链的方法。

重链剖分选择子树大小最大的点作为重儿子点;而长链剖分每次挑选子树深度最大的点作为重儿子点。

算法概述

其实和重链剖分差不多,无非选择重儿子的标准变成了子树深度最大的点。

重链剖分的一些概念也可以直接搬到长链剖分上来:

  • 一个点到其重儿子的边称为重边
  • 一个点到其轻儿子的边称为轻边
  • 重儿子相连形成的链称为长链

性质

长链剖分后,一个点到根节点的路径上,最多经过 \(O(\sqrt n)\) 条轻边。


所以这个东西和重链剖分相比,有什么特别的作用呢?

一个非常经典的应用就是求树上一个点的 \(k\) 级祖先。

树上 k 级祖先

树上一个点的 \(k\) 级祖先可以采用传统的倍增方法求,时间复杂度 \(O(n \log n)-O(\log n)\)。

当然也可以直接重链剖分后,不停在重链上跳,时间复杂度 \(O(n)-O(\log n)\)。

有没有更快的方法呢?

我们对整棵树进行长链剖分,顺带完成以下预处理:

  1. 倍增求出每个点的 \(2^i\) 级祖先。
  2. 对于每条重链的链顶节点,设其所在的重链长度为 \(l\),求出这个点向上的 \(l\) 个祖先和向下的 \(l\) 个儿子。

剖分后,容易发现点 \(u\) 的 \(k\) 级祖先所在的重链长度一定不小于 \(k\)(否则重链可以直接选择经过点 \(u\),长度还变长了)。

令 \(x=\left \lfloor \log k \right \rfloor\),我们先跳 \(2^x\) 级。

跳完之后我们还需要再跳 \(k-2^x\) 级(如果是负数的话意味着我们要往下跳,否则还是往上跳)。而这部分在预处理的时候已经求出来了,因此直接利用预处理的信息就可以了。

时间复杂度 \(O(n \log n)-O(1)\)。

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef unsigned ui;
struct gen
{
 ui s;
 void init(ui seed)
 {
  s=seed;
 }
 ui next()
 {
  ui x=s;
  x^=x<<13;
  x^=x>>17;
  x^=x<<5;
  return s=x;
 }
}g;
int fa[5000005][25],dep[5000005],maxd[5000005],son[5000005],top[5000005];
vector<int> up[5000005],down[5000005];
vector<int> e[5000005];
void dfs1(int u,int f)
{
 dep[u]=maxd[u]=dep[f]+1;
 fa[u][0]=f;
 for(int k=1;k<=23;k++)
  fa[u][k]=fa[fa[u][k-1]][k-1];
 for(auto v:e[u])
 {
  dfs1(v,u);
  if(maxd[v]>maxd[son[u]])
   son[u]=v,maxd[u]=maxd[v];
 }
}
void dfs2(int u,int t)
{
 top[u]=t;
 if(u==t)
 {
  for(int i=0,p=u;i<=maxd[u]-dep[u];i++,p=fa[p][0])
   up[u].push_back(p);
  for(int i=0,p=u;i<=maxd[u]-dep[u];i++,p=son[p])
   down[u].push_back(p);
 }
 if(son[u])dfs2(son[u],t);
 for(auto v:e[u])
  if(v!=son[u])dfs2(v,v);
}
int get_kth(int x,int k)
{
 if(!k)return x;
 int t=log2(k);
 k-=1<<t,x=fa[x][t];
 k-=dep[x]-dep[top[x]],x=top[x];
 if(k>=0)return up[x][k];
 else return down[x][-k];
}
int main()
{
 int n,q,root;
 ui s;
 cin>>n>>q>>s;
 g.init(s);
 for(int i=1;i<=n;i++)
 {
  int f;
  cin>>f;
  if(f==0)root=i;
  else e[f].push_back(i);
 }
 dfs1(root,0);
 dfs2(root,root);
 long long ans=0,lastans=0;
 for(int i=1;i<=q;i++)
 {
  int x=(g.next()^lastans)%n+1,k=(g.next()^lastans)%dep[x];
  ans^=(i*(lastans=get_kth(x,k)));
 }
 cout<<ans<<endl;
 return 0;
}

长链剖分优化 DP

这个采用了启发式合并的思想。大概思路是对于一个点,先求出其所在重链的信息,随后将其他链的信息合并到这条重链上。

CF1009F 就是一道不错的例题。

题意是给一棵树,对于每个点 \(u\) 求出一个最小深度 \(d\),使得 \(u\) 的 \(d\) 级子节点最多。

一道非常不错的长链剖分练手题。

首先是常规的 DP:设 \(f_{i,j}\) 表示点 \(i\) 的 \(j\) 级子节点的数量。

转移方程很显然(其中 \(v\) 是 \(i\) 的子节点):

$$f_{i,j}=\sum f_{v,j-1}$$

边界是 \(f_{i,0}=1\)。

这样做的时间复杂度是 \(O(n^2)\) 的,需要优化。

这时候长链剖分就登场了(实际上是树上启发式合并的思路)。

我们对于一个节点,先遍历它的重儿子,将重儿子的结果合并(说是合并,其实直接继承了重儿子的结果,并添加了当前点的信息)到当前点上。

接下来我们遍历这个点的其他轻儿子,将这些轻儿子的结果并到当前节点上。

每条重链都只合并了一次,故时间复杂度为 \(O(n)\)。


题解区似乎没有非指针版的实现?其实用 vector 也是可以搞的。

思路仍然是用 vector 存下每个点的信息。不过有几个特殊之处:

  1. 按深度递增的顺序存储的话,因为合并重儿子信息时要在开头插入元素,效率低下。所以考虑按深度递减的顺序存储信息。
  2. 合并重儿子信息的时候,直接用 swap 交换而不是复制,在时间和空间上都更优(swap 交换 vector 的时间复杂度是 \(O(1)\) 的)。
#include <cstdio>
#include <vector>
using namespace std;
vector<int> e[1000005],f[1000005];
int fa[1000005],len[1000005],son[1000005];
int ans[1000005];
void dfs1(int u,int f)
{
 fa[u]=f;
 for(auto v:e[u])
  if(v!=f)
  {
   dfs1(v,u);
   if(len[v]>=len[son[u]])
    son[u]=v,len[u]=len[v]+1;
  }
}
void dfs2(int u)
{
 if(son[u])
 {
  dfs2(son[u]);
  swap(f[u],f[son[u]]);//直接交换,降低时间空间开销
  f[u].push_back(1);//尾部插入深度为零的结果
  ans[u]=ans[son[u]];
  if(f[u][ans[u]]==1)ans[u]=len[u];
  for(auto v:e[u])
  {
   if(v==fa[u]||v==son[u])continue;
   dfs2(v);
   for(int i=len[v];i>=0;i--)
   {
    int tmp=i+len[u]-len[v]-1;
    f[u][tmp]+=f[v][i];
    if(f[u][tmp]>f[u][ans[u]]||(f[u][tmp]==f[u][ans[u]]&&tmp>ans[u]))
     ans[u]=tmp;//这里存储的是最优解在数组对应的位置,结果需要倒过来
   }
  }
 }
 else
 {
  f[u].push_back(1);
  ans[u]=0;
 }
}
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<n;i++)
 {
  int u,v;
  scanf("%d%d",&u,&v);
  e[u].push_back(v);
  e[v].push_back(u);
 }
 dfs1(1,0);
 dfs2(1);
 for(int i=1;i<=n;i++)
  printf("%d\n",len[i]-ans[i]);
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据