圆方树-学习笔记
i207M
2018-11-26 16:47:58
## 圆方树
对于一个仙人掌，它的圆方树如下定义：
首先分为了两类点，一类是圆点，一类是方点。
圆点就是原仙人掌中所有的点，方点是我们新添加进去的点。
而圆方树的连边规则是这样的：
如果一条边在仙人掌中不属于任何一个环中，那么它直接圆方树中的两个圆点。
对于仙人掌中的任意一个环，则每个环上的点在圆方树上对应的圆点向这个环对应的方点连边。
------------
不用构建圆方树的简单写法：
### 仙人掌的最大独立集
~~输出答案的时候取的是min...~~
有一种纯DFS的方法，但是我们要用圆方树！
[Blog](https://www.cnblogs.com/cjyyb/p/9090499.html)
对于DFS树上的树边，我们像树形DP一样求，当DP到一个环的顶端时，我们把环拿出来，单独DP一边，枚举顶端选、不选。
```cpp
namespace i207M
{
#define N 600005
#define int LL
int n,m;
int v[N<<1],nx[N<<1],head[N],cnte;
il void adde(int uu,int vv)
{
v[++cnte]=vv,nx[cnte]=head[uu],head[uu]=cnte;
}
int f[N][2];
int fa[N],dfn[N],low[N],dk;
void dp(int x,int y)
{
int f0=0,f1=0;
for(ri i=y; i!=x; i=fa[i])
{
int t0=f[i][0]+max(f0,f1),t1=f[i][1]+f0;
f0=t0,f1=t1;
}
f[x][0]+=max(f0,f1);
f0=-(1<<30),f1=0;
for(ri i=y; i!=x; i=fa[i])
{
int t0=f[i][0]+max(f0,f1),t1=f[i][1]+f0;
f0=t0,f1=t1;
}
f[x][1]+=f0;
}
void tarjan(int x,int ff)
{
fa[x]=ff;
dfn[x]=low[x]=++dk;
f[x][1]=1;
for(ri i=head[x]; i; i=nx[i])
if(v[i]!=ff)
{
if(!dfn[v[i]]) tarjan(v[i],x),low[x]=min(low[v[i]],low[x]);
else low[x]=min(dfn[v[i]],low[x]);
if(dfn[x]<low[v[i]])
f[x][0]+=max(f[v[i]][0],f[v[i]][1]),f[v[i]][1]+=f[v[i]][0];
}
for(ri i=head[x]; i; i=nx[i])
if(fa[v[i]]!=x&&dfn[x]<dfn[v[i]])
dp(x,v[i]);
}
signed main()
{
#ifdef M207
freopen("in.in","r",stdin);
#endif
in(n),in(m);
for(ri i=1,a,b; i<=m; ++i)
{
in(a),in(b);
adde(a,b), adde(b,a);
}
tarjan(1,0);
out(max(f[1][0],f[1][1]));
return 0;
}
}
```
### 仙人掌直径
和上一题类似，对环单独考虑，拉出来DP，更新ans，并计算环顶的f值。
```cpp
void dp(int x,int y)
{
int cnth=0;
for(int i=y; i!=x; i=fa[i]) h[++cnth]=i; h[++cnth]=x;
reverse(h+1,h+1+cnth);
for(int i=1; i<=cnth; ++i) h[i+cnth]=h[i];
int hd=1,tl=0;
for(ri i=1; i<=(cnth<<1); ++i)
{
while(hd<=tl&&q[hd]<i-cnth/2) ++hd;
if(hd<=tl) ans=max(f[h[q[hd]]]+i-q[hd]+f[h[i]],ans);
while(hd<=tl&&f[h[q[tl]]]-q[tl]<f[h[i]]-i) --tl;
q[++tl]=i;
}
for(ri i=y; i!=x; i=fa[i]) f[x]=max(f[i]+min(dep[i]-dep[x],dep[y]-dep[i]+1),f[x]);
}
```
------------
### 仙人掌最短路
是NOIP前的考试题，可以树上倍增做。
如果用圆方树，我们要建出树来：
圆圆边和原仙人掌是同构的，圆方边的权值定义如下：
我们知道方点的父亲一定是圆点(转换为有根树之后)，
这样子把每条圆方边的权值赋为到达方点父亲的最短路径就好啦。
## 广义圆方树
之前的圆方树都是在仙人掌上建立的，其实普通的无向图也可以建立圆方树，即广义圆方树。将图中的每个点双（即使大小为2），都新建一个节点。
**圆方树一定是方点和原点相间**。
盗图：
### CF487E Tourists
求无向图两点间的所有简单路径的权值最小值。权值会修改。
首先我们不考虑修改，再来想想这道题目。
我们既然要求的是最小值，那么，在经过一个点双的时候，走的一定是具有较小权值的那一侧。
所以说，我们可以让所有的方点表示它所在的点双的最小权值，这样子只需要对于圆方树树链剖分之后维护链的最小值就行了。
好的，回归带修改，无非是要动态的维护一下方点的最小权值了。
你问我怎么动态维护若干个值的最小值？搞个multiset不就好了吗？
但是，现在问题又来了，如果每次修改一个点的权值(这个点当然是圆点啦)，那么，必定会修改所有和它相邻的方点，如果是一个菊花树，然后我们拼命修改根节点，这样子复杂度就起飞了。
现在让我们打开脑洞，大力思考一下怎么办？
我们强行让方点的权值不包括它的父亲(也就是只算它的儿子)。如果求解的时候LCA是方点，则额外计算一下方点父亲的权值。
这样子每个圆点在修改的之后只需要向上修改给父亲方点啦！
-By [yyb](https://www.cnblogs.com/cjyyb/p/9097906.html)
**这道题的重点就是为了保证复杂度，修改每个方点维护的数据，使得便于修改！**