圆方树总结以及利用

前言：

听说圆方树在竞赛中的应用越来越多，于是在认真听了jz大佬的讲课后写了此篇文章。

圆方树：

圆方树是用来解决仙人掌树的一种数据结构，可以把仙人掌树转化成一棵较普通树，然后运用以前树的性质和自己动脑思考来解决题目。
//广义圆方树听说可以做图的情况

构造方法：

利用tarjan算法，找出一棵仙人掌树的环上的点（成为圆点），把一个环上的圆点各连出一条边到新的方点上（自建）。然后圆点之间的边全部都删掉。such as：

这样看起来是不是就很像圆方树了（有园的点也有方的点，他还是一棵树）。

具有的性质：

1.他是一棵无根树，不管用哪个点为根，他的形态是一样的。
2.圆方树的子树个数就是原来仙人掌树的仙人掌的个数。
3.方点不会和方点连接。
//好像没什么用

应用：

最短路
动态规划 ：仙人掌的直径，最大独立子集。
虚仙人掌（不会）
点分治（不会）
链剖分（不会）

例题1

最短路例题：jzoj5287，bzoj2125.

我们先构建出圆方树，然后利用树上最短路lca的方法求出最短路径（好像没了….）。
构建细节，先制定一个圆点为根，然后每个方点向父亲节点连一条长度为零的边，方点的儿子向方点连一条长度为在原本仙人掌树仙人掌中离方点父亲最近的距离（环有两条路可以到方点父亲）。
同时在lca完后，如果跳到的是一个圆点上就和原本的树上最短路没什么区别，但是如果结束点在一个方点上，那么这两个点就是在同一个仙人掌中间，统计距离的时候就要分类讨论。1.他们两个点在原来仙人掌中间的同一侧2.他们两个点在原来仙人掌的不同侧（真的没了）。

代码：

例题2

dp例题：bzoj 4316
给你一张仙人掌图，求出仙人掌上的最大独立子集为多少。
这题好像比较简单，先构建出圆方树，没有方点就是瞎几把搞，dp[i，0/1]为这个点选或者不选的最大独立子集。如果有方点那要怎么办呢，回归仙人掌，你会发现连向方点的边就是一个环上的，方点的父亲可能会影响到方点的一个儿子，那我们就可以设出方点的dp方程dp[i,0/1,0/1]，为方点的父亲选不选和方点选不选（还不确定）。

代码：

例题3

杂题：jzoj 3960