圆方树

圆方树是个好东西，可以将树上的题目出到一般图上~~(就是毒瘤)~~。今年的CCFWC上就新出了一种快速建树方法。圆方树变得比以前不那么深不可测，作用也拓展了。 ## 1 定义 #### 1.1 圆方树在仙人掌上的定义 这个还挺简单的。 原来的点都视为圆点。对于每个**简单环**，用一个方点来代替这个环，并且该方点和环上所有的圆点连边。可以简单证明，这样建出来的图一定是一棵树。因为它由圆点和方点组成，所以称为圆方树。 #### 1.2 圆方树在一般图上的定义 因为一般图没有仙人掌优秀的性质(即每条边属于且仅属于一个简单环)，所以按照上文的定义建出的不一定是一棵树。我们需要修改它的定义。 原来的点都视为圆点。但是此时，**不再是对于简单环**，而是对于每个**边双**，用一个方点代替它，并且该方点和边双内的所有圆点连边。同样可以证明，建出来的图是一棵树。我们同样将它称为圆方树。 另外，为了方便处理，我们将**原图中的一条割边也视为一个点双**。 如下图，左图是原图，右图为左图的圆方树。(为了方便，右图每个点的标号增大了10)右图中的黑点表示圆点，白点表示方点。  ## 2 建树 #### 2.1 描述 主要采用$tarjan$边双魔改来建树。 需要的数组和tarjan边双的一样，但是注意要区分原图的边和圆方树的边。 算法仍然是基于$dfs$序的。对于每个点，求出其$dfs$序$dfn$和通过返祖边最远可达的点标号$low$。并在$dfs$的过程中用栈记录一路上访问的节点。如果某条边$(u,v)$满足$low[v]\ge dfn[u]$，则$u,v$及其中的所有点都属于一个边双。对于该边双新建一个节点代表该边双，将该点的父节点设为$u$(如果没有需求则不需要)且连边，然后将$v$之后的栈内所有元素**(包括$v$)** 全部和该边双连边，父节点为该边双(还是没有需求就不连)。这样就可以在$O(n)$的时间内将圆方树建出。注意，具体每个边双有哪些点**不重要**，可以不记录。 #### 2.2 具体代码实现 ```cpp void tarjan(int u,int ff) { dfn[u]=low[u]=++dfc;sta[++tp]=u; for(register int v=p.head[u];v;v=p.p[v].nxt) { if(!dfn[p.p[v].v]) { tarjan(p.p[v].v,u); Chkmin(low[u],low[p.p[v].v]); if(low[p.p[v].v]>=dfn[u]) { fa[0][++cnt]=u,q.add(u,cnt); static int las; do { las=sta[tp--]; fa[0][las]=cnt,q.add(cnt,las); }while(las^p.p[v].v); } }else if(p.p[v].v^ff)Chkmin(low[u],dfn[p.p[v].v]); } }//注意此处的fa数组是二维的，作用是倍增。一般只需要一维就可以了 //好像代码比tarjan求边双要短 ``` ## 3 具体作用 主要用于毒瘤题。 树形$dp\to$一般图$dp$ 虚树$dp\to$虚圆方树$dp$ 树链剖分$\to$圆方树剖分 树分治$\to$圆方树分治 (以下省略一大波毒瘤题) ## 4 例题 #### 4.1 [luogu P4320] 道路相遇 [就是这个](https://www.luogu.org/problemnew/show/P4320)。 分析发现就是求路径必经点数，也就是圆方树上圆点个数。套用倍增求解即可。时间复杂度$O(n+qlogn)$。 代码: ```cpp #include<bits/stdc++.h> #define For(i,a,b) for(i=(a);i<=(b);++i) #define Forward(i,a,b) for(i=(a);i>=(b);--i) #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define Chkmin(a,b) a=a<b?a:b #define Chkmax(a,b) a=a>b?a:b using namespace std; template<typename T>inline void read(T &x){ T s=0,f=1;char k=getchar(); while(!isdigit(k)&&k^'-')k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } void file(void){ #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } const int MAXN=1e6+7,MAXM=2e6+7; static int n,m,Q,e; struct edge { int v,nxt; }; static struct edges { edge p[MAXM]; int head[MAXN]; inline void add(int u,int v){this->p[++e]=(edge){v,head[u]};this->head[u]=e;} }p,q; static int dfn[MAXN],low[MAXN],bel[MAXN],cnt,sta[MAXN],tp,dfc,fa[19][MAXN]; void tarjan(int u,int ff) { dfn[u]=low[u]=++dfc;sta[++tp]=u; for(register int v=p.head[u];v;v=p.p[v].nxt) { if(!dfn[p.p[v].v]) { tarjan(p.p[v].v,u); Chkmin(low[u],low[p.p[v].v]); if(low[p.p[v].v]>=dfn[u]) { fa[0][++cnt]=u,q.add(u,cnt); static int las; do { las=sta[tp--]; fa[0][las]=cnt,q.add(cnt,las); }while(las^p.p[v].v); } }else if(p.p[v].v^ff)Chkmin(low[u],dfn[p.p[v].v]); } } static int sm[21][MAXN],dep[MAXN]; void caldep(int u) { dep[u]=dep[fa[0][u]]+1; for(register int v=q.head[u];v;v=q.p[v].nxt)caldep(q.p[v].v); } inline void init() { memset(q.head,0,sizeof q.head); memset(p.head,0,sizeof p.head); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(bel,0,sizeof bel); memset(sm,0,sizeof sm); memset(fa,0,sizeof fa); read(n);read(m); static int u,v; Rep(i,1,m)read(u),read(v),p.add(u,v),p.add(v,u); e=dfc=tp=0;cnt=n; tarjan(1,0); Rep(i,1,n)sm[0][i]=1; Rep(j,1,19)Rep(i,1,n) { sm[j][i]=sm[j-1][i]+sm[j-1][fa[j-1][i]]; fa[j][i]=fa[j-1][fa[j-1][i]]; } caldep(1); } inline int lca(int u,int v) { if(dep[u]<dep[v])swap(u,v); static int ans;ans=0; Repe(i,19,0)if(dep[u]-dep[v]>=(1<<i))ans+=sm[i][u],u=fa[i][u]; if(u==v)return ans+sm[0][u]; Repe(i,19,0)if(fa[i][u]^fa[i][v])ans+=sm[i][u]+sm[i][v],u=fa[i][u],v=fa[i][v]; return ans+sm[0][u]+sm[0][v]+sm[0][fa[0][u]]; } void dfs_print(int u) { for(register int v=q.head[u];v;v=q.p[v].nxt) { printf("%d %d\n",u,q.p[v].v); dfs_print(q.p[v].v); } } inline void solve() { //dfs_print(1); read(Q); static int u,v; Rep(i,1,Q) { read(u),read(v); printf("%d\n",lca(u,v)); } } int main(void){ file(); init(); solve(); cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ``` #### 4.2 [SDOI2018]战略游戏 [不会是这个吧](https://www.luogu.org/problemnew/show/P4606) 发现就是上一道题套用虚树$dp$。直接做就可以了。 代码: ```cpp #include<cstdio> #include<cctype> #include<cstdlib> #include<algorithm> #include<cstring> #include<iostream> #include<vector> #include<cassert> #define Rep(i,a,b) for(register int i=(a);i<=(b);++i) #define Repe(i,a,b) for(register int i=(a);i>=(b);--i) #define rep(i,a,b) for(register int i=(a);i<(b);++i) #define pb push_back #define mx(a,b) (a>b?a:b) #define mn(a,b) (a<b?a:b) typedef unsigned long long uint64; typedef unsigned int uint32; typedef long long ll; using namespace std; namespace IO { const uint32 Buffsize=1<<15,Output=1<<24; static char Ch[Buffsize],*S=Ch,*T=Ch; inline char getc() { return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++); } static char Out[Output],*nowps=Out; inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;} template<typename T>inline void read(T&x) { x=0;static char ch;T f=1; for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1; for(;isdigit(ch);ch=getc())x=x*10+(ch^48); x*=f; } template<typename T>inline void write(T x,char ch='\n') { if(!x)*nowps++='0'; if(x<0)*nowps++='-',x=-x; static uint32 sta[111],tp; for(tp=0;x;x/=10)sta[++tp]=x%10; for(;tp;*nowps++=sta[tp--]^48); *nowps++=ch; if(nowps-Out>1e7)flush(); } } using namespace IO; void file() { #ifndef ONLINE_JUDGE FILE*DSD=freopen("water.in","r",stdin); FILE*CSC=freopen("water.out","w",stdout); #endif } inline void Chkmin(int&u,int v){u>v?u=v:0;} const int MAXN=2e5+7; static int n,m; vector<int>ed[MAXN],Ed[MAXN]; static int dfn[MAXN],dfs_clock,low[MAXN],sta[MAXN],tp,e; void tarjan(int u,int fr) { dfn[u]=low[u]=++dfs_clock,sta[++tp]=u; for(int v:ed[u])if(!dfn[v]) { tarjan(v,u),Chkmin(low[u],low[v]); if(low[v]>=dfn[u]) { register int cur=++e; Ed[cur].resize(0),Ed[u].pb(cur); do{Ed[cur].pb(sta[tp--]);}while(sta[tp+1]^v); } } else if(v^fr)Chkmin(low[u],dfn[v]); } inline void init() { read(n),read(m); static int u,v; Rep(i,1,n)dfn[i]=low[i]=0,ed[i].resize(0),Ed[i].resize(0);e=n; Rep(i,1,m)read(u),read(v),ed[u].pb(v),ed[v].pb(u); dfs_clock=0,tarjan(1,0); } static int dp[MAXN]; namespace LCA { static int efn[MAXN],nx[19][MAXN<<1],efs_clock,dep[MAXN]; void efs(int u) { nx[0][efn[u]=++efs_clock]=u; for(int v:Ed[u]) { dep[v]=dep[u]+1,dp[v]=dp[u]+(v<=n); efs(v); nx[0][++efs_clock]=u; } } inline int fixmx(int u,int v){return dep[u]<dep[v]?u:v;} inline void initial() { dep[1]=dp[1]=1,efs_clock=0,efs(1); int mxlg=31-__builtin_clz(efs_clock); Rep(j,1,mxlg)Rep(i,1,efs_clock-(1<<j-1)+1) nx[j][i]=fixmx(nx[j-1][i],nx[j-1][i+(1<<j-1)]); } inline int getlca(int u,int v) { int l=efn[u],r=efn[v]; if(l>r)swap(l,r); int k=31-__builtin_clz(r-l+1); return fixmx(nx[k][l],nx[k][r-(1<<k)+1]); } } using LCA::initial; using LCA::getlca; static int Q,k,nd[MAXN<<1]; inline bool cmp(const int&a,const int&b){return LCA::efn[a]<LCA::efn[b];} inline void solve() { initial(); read(Q); register int ans; Rep(i,1,Q) { read(k),ans=-k; Rep(j,1,k)read(nd[j]); sort(nd+1,nd+k+1,cmp); Rep(j,1,k-1)nd[k+j]=getlca(nd[j],nd[j+1]); sort(nd+1,nd+k+k,cmp); k=unique(nd+1,nd+k+k)-nd-1; tp=0; Rep(j,1,k) { while(tp&&getlca(sta[tp],nd[j])^sta[tp]) ans+=tp>1?dp[sta[tp]]-dp[sta[tp-1]]:0,--tp; sta[++tp]=nd[j]; } while(tp)ans+=tp>1?dp[sta[tp]]-dp[sta[tp-1]]:0,--tp; ans+=sta[1]<=n; write(ans); } } int main() { file(); static int _;read(_); while(_--)init(),solve(); flush(); return 0; } ``` #### 4.3 [APIO2018]铁人两项 [点我](https://www.luogu.org/problemnew/show/P4630) 发了题解，具体做法及代码见[这篇博客](https://www.luogu.org/blog/user7035/solution-p4630)。