圆方树学习笔记
lindongli2004 · · 个人记录
一 . 分类
分为圆方树与广义圆方树，前者处理仙人掌，后者处理无向图，本文只介绍广义圆方树。二 . 构建
1. Tarjan求点双联通分量。
2. 对于每个点双新建一个方点，向每个圆点（点双中的点）连边，并保持原图中的边不变。如下图：
这样就可以用圆点维护点上信息，方点维护点双信息了。三 . 性质
- 一条简单路径不可能有两个方点相邻，比如：圆方圆圆方，方圆方圆方。
- 原图中的割点即为度数>1的圆点。
更多的性质请大家补充。四 . 应用
[ APIO2018 ] Duathlon 铁人两项
题意：
给定一张无向图，统计合法三元组 (s,c,f) 个数，一个三元组是合法的，当且仅当存在一条 s->f 的简单路径经过 c 。题解：
1. 固定 s,f ,合法的 c 的数量即为 s,f 之间点双的点数和-2（s,f两点不算在内）
2. 建出圆方树，令val[x](圆点点权)=-1，val[y](方点点权)=cnt[y](点双点数)。
3. f[x](一个点的贡献)=val[x](点权)*road[x](经过 x 的边数)*2（(s,c,f)有序）
4. 所以 ans(答案)=$\sum_{x=1}^{sum(点双个数)+n}f[x]$
5. 求 road[x],f[x] 用 树形 DP , val[x] 用 Tarjan 即可。
6. 备注：详细的求法在代码注释中。代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=502019;
typedef long long LL;
int n,sum,m,tot,tot1,top,siz; LL ans;
int val[N],stk[N],low[N],dfn[N],v[N],v1[N],sz[N];
struct Edge{int to,next;}e[N<<2],e1[N<<1];
// sum 是方点的编号,siz 是当前连通块的点数，e 是新图，e1 是原图 .
inline void add1(int x,int y){
e1[++tot1].to=y; e1[tot1].next=v1[x]; v1[x]=tot1;
}
inline void add2(int x,int y){
e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;
}
inline int read(){ // 快读
int x(0); char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void tarjan(int x){ // Tarjan 求点双
stk[++top]=x;
low[x]=dfn[x]=++siz;
for(int p=v1[x];p;p=e1[p].next){
int kp=e1[p].to;
if(!dfn[kp]){
tarjan(kp); low[x]=min(low[x],low[kp]);
if(low[kp]>=dfn[x]){ // 连边
val[++sum]=1; int th;
do{
th=stk[top--]; ++val[sum];
add2(sum,th); add2(th,sum);
}while(th!=kp);
add2(sum,x); add2(x,sum);
}
}
else low[x]=min(low[x],dfn[kp]);
}
}
void dfs(int x,int fa=0){
sz[x]=(x<=n);
for(int p=v[x];p;p=e[p].next){
int kp=e[p].to;
if(kp==fa)continue;
dfs(kp,x);
// 此处可以自己手推一下，统计答案 .
// 具体来说经过 x 的路径条数(road[x])分为两部分 .
// 一部分是 儿子->儿子 (Part1) , 另一部分是 父亲->儿子 Part2) .
ans+=2ll*val[x]*sz[x]*sz[kp];
sz[x]+=sz[kp]; // Part1
// 举个例子,点 x 有四个儿子, size 分别为 a,b,c,d 则
// road[x]=a*b+a*c+a*d+b*c+b*d+c*d+(Part2)=a*(b+c+d)+b*(c+d)*c*d+(Part2) .
} ans+=2ll*val[x]*sz[x]*(siz-sz[x]); // Part2
}
int main()
{
sum=n=read(); m=read();
for(int x,y,i=1;i<=m;i++)
x=read(),y=read(),add1(x,y),add1(y,x);
for(int i=1;i<=n;i++)val[i]=-1;
for(int i=1;i<=n;i++) // 核心代码
if(!dfn[i])siz=0,tarjan(i),dfs(i);
printf("%lld\n",ans);
return 0;
}
[ CF Round #278 ] Tourists
题意
给定一张带权无向图，两个操作
- C a w 将点 a 的点权改为 w 。
- A a b 询问 a->b 所有合法简单路径上点权的最小值。题解
1. 不考虑 C 操作。
2. A 操作可以把圆方树建出来，方点的权值为其所对应点双内点权最小值，这样就转化为一个链上最值，树剖套线段树即可。
3. 考虑 C 操作。
4. 每个方点维护一个可删堆，修改一个圆点时，把对应的方点 pop 原数，push 新数，在线段树上单点修改即可。
5. 上面的做法是对的，但是会 TLE 。因为一个圆点可能对应多个方点，比如最上面的那张图。
6. 我们可以规定只修改圆点的父亲(一定是个方点)，为保证正确性，最后在 LCA 处特判一下即可。
7. 备注：细节在代码注释中。代码
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=302018,INF=2e9;
int n,m,aq,sum,cnt,size,top1,tot1,tot;
int v[N],v1[N],stk[N],dfn[N],low[N],fa[N],id[N],son[N],top[N],dep[N],siz[N],wt[N];
struct Edge{int to,next;}e[N<<2],e1[N<<1];
void add1(int x,int y){
e1[++tot1].to=y; e1[tot1].next=v1[x]; v1[x]=tot1;
}
void add(int x,int y){
e[++tot].to=y; e[tot].next=v[x]; v[x]=tot;
}
struct My_Heap{// 可删堆
// 思路就是维护一个加入堆(q1)，一个删除堆(q2)。
priority_queue<int,vector<int>,greater<int> > q1,q2;
inline void push(int x){q1.push(x);}// push 时加入到 q1 中
inline void pop(int x){q2.push(x);}// pop 时加入到 q2 中
inline int get(){
while(!q1.empty() && !q2.empty() && q1.top()==q2.top())q1.pop(),q2.pop();// 查找堆顶时 check 如果当前 q1.top()==q2.top() 就说明这个元素已经应当被删除了，所以 q1,q2 同时 pop 掉。
return q1.top();
}
}w[N];
struct Tr{int l,r,dt;}tr[N<<3];
void tarjan(int x){// Tarjan 求点双
stk[++top1]=x;
dfn[x]=low[x]=++size;
for(int p=v1[x];p;p=e1[p].next){
int kp=e1[p].to;
if(!dfn[kp]){
tarjan(kp); low[x]=min(low[x],low[kp]);
if(low[kp]>=dfn[x]){
++sum; int th;// 连边
do{
th=stk[top1--];
add(th,sum); add(sum,th);
}while(th!=kp);
add(x,sum); add(sum,x);
}
}
else low[x]=min(low[x],dfn[kp]);
}
}
// dfs1,dfs2 都是树剖的预处理
void dfs1(int x,int ff,int d){
dep[x]=d; fa[x]=ff; siz[x]=1;
int mxson=-1;
for(int p=v[x];p;p=e[p].next){
int kp=e[p].to;
if(kp!=ff){
if(x>n)w[x].push(w[kp].get());// 方点预处理
dfs1(kp,x,d+1);
if(siz[kp]>mxson)
mxson=siz[kp],son[x]=kp;
siz[x]+=siz[kp];
}
}
}
void dfs2(int x,int tp){
top[x]=tp;
id[x]=++cnt; wt[cnt]=w[x].get();
if(son[x])dfs2(son[x],tp);
else return;
for(int p=v[x];p;p=e[p].next){
int kp=e[p].to;
if(kp!=fa[x] && kp!=son[x])
dfs2(kp,kp);
}
}
// 以下为线段树求区间最小值
void updata(int k){
tr[k].dt=min(tr[k<<1].dt,tr[k<<1|1].dt);
}
void build(int k,int l,int r){
tr[k].l=l; tr[k].r=r;
if(l==r)return tr[k].dt=wt[l],void();
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
updata(k);
}
void change(int k,int lc,int vl){
if(tr[k].l==tr[k].r)return tr[k].dt=vl,void();
int mid=(tr[k].l+tr[k].r)>>1;
if(lc<=mid)change(k<<1,lc,vl);
else change(k<<1|1,lc,vl);
updata(k);
}
int query(int k,int ql,int qr){
if(ql<=tr[k].l && qr>=tr[k].r)return tr[k].dt;
int mid=(tr[k].l+tr[k].r)>>1,ans=INF;
if(ql<=mid)ans=min(ans,query(k<<1,ql,qr));
if(qr>mid)ans=min(ans,query(k<<1|1,ql,qr));
return ans;
}
void newit(int x,int dl,int ad){// 对于一个点，点权的插入与删除
w[x].pop(dl); w[x].push(ad);
change(1,id[x],w[x].get());
}
void Trchange(int x,int y){// 修改点权
// for(int i=0;i<bl[x].size();i++)
// newit(bl[x][i],w[x].get(),y);
// 上面是 TLE 的代码，下面是 AC 的代码
newit(fa[x],w[x].get(),y);
newit(x,w[x].get(),y);
}
int Trquery(int x,int y){
int res=INF;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res=min(res,query(1,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
if(x>n)res=min(res,w[fa[x]].get());// 特判 LCA 是方点的情况。
// 如果 LCA 是方点，需要将 fa[LCA] 这个圆点计入答案。
// 因为方点只维护了儿子的信息，父亲属于同一个点双但是没有维护，所以这里计入答案。
return min(res,query(1,id[x],id[y]));
}
inline int read(){// 快读
int x(0); char ch=getchar();
while(ch<'0' || ch>'9')ch=getchar();
while(ch>='0' && ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
void pr(int x){if(x>9)pr(x/10);putchar(x%10+'0');}// 快输
int main()
{
sum=n=read(); m=read(); aq=read();
for(int i=1;i<=n;i++)w[i].push(read());
for(int x,y,i=1;i<=m;i++)
x=read(),y=read(),add1(x,y),add1(y,x);
tarjan(1); dfs1(1,0,0); dfs2(1,1); build(1,1,sum); //核心代码
while(aq--){
char c; scanf("%c",&c);
int x=read(),y=read();
if(c=='C')Trchange(x,y);
else pr(Trquery(x,y)),putchar('\n');
}
return 0;
}六 . 总结
圆方树的核心在于圆点和方点，只要想清楚这两者的用途，大部分题目就可以迎刃而解了。
欢迎大家指正本 blog 的错误之处。