type
status
date
slug
summary
tags
category
icon
password
，即最近公共祖先。
如上图，3，6的最近公共祖先是2；
众所周知， 的主流求法有 4 种，而我只会树刨这一种。。
树链刨分
首先要建图，还是使用邻接表
建完后要来对树进行刨分，在此之前要记录好根节点。
第一次记录父亲节点·叶子数量·重儿子（最长链）·深度（节点间的距离）
紫色标记的是重链。
这时注意到只统计了父节点，而跳时能够跳到这条链的顶部节点最好，而且可以借此将树按一定顺序映射到区间上便于进行区间处理，这顺序叫做序。
第二次便要完成以上操作。
之后求的过程就方便了，只需要跳节点就可以。
时间复杂度
易知根节点到任意节点路径上的轻链数小于
所以复杂度为
带前缀和权值
重链剖分
通过序建立线段树来维护树上问题。
代码
例题
- Author:Grimner
- URL:https://tangly1024.com/article/example-24
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!