树链相关问题

轻重链剖分求LCA

• 轻重链剖分，就是将一棵树划分为多个互不相交的链
• 两遍，复���度
•  维护出该节点的直接父亲，在通过其儿子节点中重量最大的（即以其为根的子树大小最大）作为重儿子，也就是该点所在树链的直接儿子，同时维护深度
•  维护每条链的链头，用于处理不在同一条链上的两点求，实现直接跳过一条链
• 若两点在一条链上，则输出深度较低的点
• 若两点不在一条链上，则两点中链头深度较大往上跳，直到两个跳到同一条链上
• 复杂度

  虚树

  • 通过关键点建树，删去关键点影响不到的点
  • 单调栈维护
  • 实际单调栈中维护了一条树链
  • 根先入栈，然后关键点按照序依次入栈
  • 设当前加入的关键点为，当前栈顶为，求其
  • 若，则在单调栈维护的树链上，直接入栈
  • 若，则弹出栈顶，并将与新栈顶连边，然后接着弹栈顶
  • 若当前栈顶的序小于的序，则说明栈中没有，则先将入栈，再入栈
  • 否则，一定能找到，然后将入栈
  • 最后，再将单调栈中维护的树链，进行连边（依次弹出，并对新栈顶连边）
  • 至此，虚树建立完毕，然后在虚树上跑树形
  • 注意，只用在每次新添入栈时，删去该点上次建树链式前向星连的边即可