[学习笔记] 基环树

发布时间 2023-06-12 17:12:27作者: SF71-H

一、基环树

基环树其实 并不是 一棵树,而是一张 \(n\) 个点 \(n\) 条边的连通图。

一般的基环树就形如一棵 \(n\) 个节点的树再加上一条非树边。

扩展. 如果基环树不连通,就变成多个基环树组成的森林了。

Method 1. 将环拎出来,环上的每一个节点都挂了一棵子树,将子树信息合并,在环上处理即可。

image

Method 2. 将那一条非树边去掉,先按照树处理,再考虑那一条非树边。

image

N 代表非树边(

二、例题

例题来源:CF711D, 洛谷 P1453, 洛谷 P2607, 洛谷 P4381, 洛谷 P1399, CF835F, 洛谷 P2081

三、参考文献

https://www.luogu.com.cn/blog/ShadderLeave/ji-huan-shu-bi-ji