圆方树学习笔记

圆方树学习笔记

听说G2的选手都会圆方树了,所以我来学习一波。

这个阶段的学习我也仅仅只是知道了圆方树是什么,比较简单的题目怎么写,但是对于一些思维难度较高,代码实现能力要求较高的题目,我还不是很会.

希望未来能越来越好!

前置知识

点双连通分量,仙人掌的定义。

什么是圆方树

点分为圆点和方点的树.

把仙人掌上的点保留,然后如果存在一个点双就新建一个方点,对于点双上的所有圆点连边。

圆方树是棵树的证明可通过:连通+(n=m+1)来证明.

如何构建圆方树

就是模拟上述定义过程.

来几道题目

Luogu5236 静态仙人掌

Luogu4244 [SHOI2008]仙人掌图 II

BZOJ4316 小C的独立集

一般的话,仙人掌问题你就需要考虑环的处理方法即可,圆点之间按照树型转移.

广义圆方树

暂不赘述

我还不会,等我写完了再更.

原文地址:https://www.cnblogs.com/fexuile/p/13025514.html