笔记 - 树

树的各类元素

包括 树上差分, 直径, 重心, 中心, LCA等

• 巡逻 典 树的直径
  启示: 需要对"重合部分"进行处理时, 可以使一些边的权取反.

• 暗之连锁 模板 树上差分 + LCA
  x 到 y 的路径上的所有边被覆盖了一次

• 雨天的尾巴 模板 典 树上差分 + 线段树合并
  x 到 y 的路径上所有点被类型 z 覆盖了一次

• 天天爱跑步 难 (待补)

• 异象石 典 DFN序 + LCA + set 的用法
  求覆盖树的某点集的最短边集

• 次小生成树 模板 MST + LCA

• Number of Simple Path 模板 基环树(总路径计数)
  一颗大小为 N 的树中, 所有路径数量为 \(\frac{N(N-1)}{2}\)

• 岛屿 典 基环树(直径)+环形DP or 内向树解法
  注意写法, 此题又 de 了一个上午