终于对仙人掌有了一点初步的理解.
仙人掌
仙人掌是什么?
仙人掌是一个无向图.
仙人掌有什么特点?
仙人掌的每条边只属于一个简单环.
下面是一个栗子
有什么用呢?
我们可以先用(tarjan)找出环,然后处理.
下面是一道例题,(BZOJ4316)
显然,在环内(dp),把答案并到根(环中(dfs)序最小的点)上,然后在环外(dp)就行了.
详细题解在这里
下面是另一道例题,(BZOJ1023)
我们用(f[u])表示到(u)的最长距离.
还是每次找到环就(dp)一番,然后再环外(dp).
环内是一个简单的用单调队列优化的区间(dp).
具体题解戳这里
圆方树
有的时候,朴素的(tarjan+dp)可能无法解决某些问题.
我们需要构造圆方树.
圆方树是什么?
对于仙人掌中所有的环,都新建一个节点,连接环上所有节点.我们称原来的点为圆点,新建的点为方点.
仙人掌上的桥就直接保留即可.
找环就(tarjan)即可.
比如上图的仙人掌,构造的圆方树长这样
(其实(7,8)号点是方点)
圆方树有一些很优秀的性质
- 圆方树是一棵树
- 圆方树中不存在方-方边.
- 圆方树是联通的(对仙人掌而言)
于是我们将仙人掌的问题转化为树上问题,可以有许许多多的解法了.