点分治

lunivia · 2023-02-22 13:29:13 · 算法·理论

点分治，一种求树上路径长度的问题。时间复杂度为 O(n\log n)。

前置知识：树的直径。

P4178

考虑暴力，直接枚举每两个端点。时间复杂度为 O(n^2)。

但是大数据过不了，例如一条链就是无法过的。

考虑找到树的重心，这样子每个节点都是小于 \log n 的大小，这样子就可以继续递归，保证最后是 O(n\log n)。

首先，找出树的重心。

然后，分两种情况讨论：经过重心和不经过重心。

然后不经过重心的就继续分治就好了。

例如，b-e 就是经过 a，但是 d-e 就没有经过，对于这种情况，我们要把 c 作为子树然后再求。

找重心代码：

void GetRoot( int x , int fa ) {
  f[ x ] = 0 , siz[ x ] = 1;
  for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
    int y = e[ i ].v;
    if( vis[ y ] || y == fa ) continue; //vis是否当过根节点
    GetRoot( y , x );
    siz[ x ] += siz[ y ];
    f[ x ] = max( f[ x ] , siz[ y ] );  //求最大子树大小
  }
  f[ x ] = max( f[ x ] , sum - siz[ x ] ); //剩下那一部分也要算上
  if( f[ x ] < f[ root ] ) root = x;  //寻找最小的
}

然后我们用树的重心跑出子树每个的深度值，放在 depth 数组里。

参考代码：

void GetDep( int x , int fa , int sum ) {
  dep[ ++tot ] = sum;
  for( int i = head[ x ] ; i ; i = e[ i ].nxt ) {
    int y = e[ i ].v;
    if( vis[ y ] || y == fa ) continue;
    GetDep( y , x , sum + e[ i ].w );
  }
}

然后将 depth 数组排序，我们就知道每个的距离了。

如果枚举每一个节点，那时间复杂度会增加。

所以要排序，然后通过双指针求出个数。

例如这个数组：

0 1 2 2 3
k=4

现在 l=1,r=5。