[洛谷P3379]【模板】最近公共祖先(LCA)[倍增, 树剖]

复习下树上常见算法… 本文中都是远古代码, 一切Bug概不负责.

lca最暴力的求法就是x,y一次次往上跳, 这样效率显然很低, 考虑优化, 有两种途经:

树上倍增

dfs预处理一个倍增找父亲节点的数组, x,y成倍的往上跳, 时间复杂度降为log级

通常树上倍增的套路都是设$latex F[i][j]$为节点$latex i$的第$latex 2^j$个父亲, 那么有$latex F[i][j]=F[[i][j-1]][j-1]$(或$latex dis[i][j]=dis[i][j-1]+dis[F[i][j-1]][j-1]$, $latex dis[i][j]$为节点$latex i$到它的的第$latex 2^j$个父亲的路径权值和 等类似的递推式), 这样就可以实现$latex O(n\log n)$一次dfs预处理后$latex \log$级查询了! 这是一种非常重要的树上倍增通法.

树链剖分

利用树链剖分把树处理成一些链, 每次跳到当前链的链顶, 直至x,y在同一条链上, 每次查询复杂度log级(一共不超过logn条重链)

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址