（廣義）圓方樹(shù) & 仙人掌 學(xué)習(xí)筆記

前言

圓方樹(shù)可用于分解仙人掌，同時(shí)也可以拿來(lái)處理點(diǎn)雙，是一個(gè)不能錯(cuò)過(guò)的知識(shí)點(diǎn)。

實(shí)現(xiàn)

先對(duì)一個(gè)無(wú)向圖跑 Tarjan 求出點(diǎn)雙，然后定義：

• 圓點(diǎn)：就是原點(diǎn)。
• 方點(diǎn)：每個(gè)點(diǎn)雙就是一個(gè)方點(diǎn)。

然后我們讓方點(diǎn)與自己點(diǎn)雙中的所有圓點(diǎn)都連上邊，就得到了圓方樹(shù)。

應(yīng)用

實(shí)現(xiàn)很簡(jiǎn)單，但是應(yīng)用并不一定。

圓方樹(shù)省略

建出圓方樹(shù)是一件非常耗時(shí)的事，有的時(shí)候這步可以直接省略，幫我們?cè)诳紙?chǎng)上節(jié)約很多時(shí)間。

P10779 BZOJ4316 小 C 的獨(dú)立集

在仙人掌上進(jìn)行 DP，但其實(shí)可以不建出圓方樹(shù)，直接在 Tarjan 算法執(zhí)行的時(shí)候 DP。

我們定義在仙人掌上：

• 葉片：大小大于 \(2\) 的點(diǎn)雙；
• 樹(shù)邊：大小等于 \(2\) 的點(diǎn)雙中連接兩原點(diǎn)的邊；

我們假設(shè)現(xiàn)在正在跑 Tarjan，進(jìn)行到了點(diǎn) \(u\)。那么對(duì)于點(diǎn) \(u\) 的某個(gè)子節(jié)點(diǎn) \(v\)，與 \(u\) 的關(guān)系有兩種可能：

1. 與 \(u\) 不同在任何一個(gè)葉片上，即 \((u,v)\) 為樹(shù)邊。
2. 與 \(u\) 同在某一個(gè)葉片上，假設(shè)它們同在的葉片為 \(leaf\)，則 \(leaf\) 中有兩個(gè)點(diǎn)與 \(u\) 有連非樹(shù)邊。

那么回到題目中，我們對(duì)于以上兩種 \(v\) 分別進(jìn)行 DP 處理：

1. 第一種很簡(jiǎn)單，就如同樹(shù)上的獨(dú)立集：

   我們可以在遍歷子節(jié)點(diǎn)的時(shí)候直接判斷出來(lái)。

   for(const int &v:g[u])if(v^fa[u]) {
   	if(!dfn[v]) {
   		fa[v]=u,tarjan(v),tomin(low[u],low[v]);
   		if(low[v]>dfn[u])f[u][0]+=max(f[v][0],f[v][1]),f[u][1]+=f[v][0];
   	} else tomin(low[u],dfn[v]);
   }
   

2. 第二種需要我們遍歷葉片：

   先找到 \(leaf\) 中的某個(gè)與 \(u\) 相連的 \(v\)，這個(gè) \(v\) 又分成兩種情況：

   • 在搜索樹(shù)中父節(jié)點(diǎn)為 \(u\)。
   • 在搜索樹(shù)中父節(jié)點(diǎn)不為 \(u\)。

   我們可以從“在搜索樹(shù)中父節(jié)點(diǎn)不為 \(u\)”的這一類 \(v\) 入手，發(fā)現(xiàn)通過(guò)仙人掌上的每個(gè)點(diǎn)雙都是一個(gè)環(huán)的性質(zhì)可以通過(guò)不斷跳父節(jié)點(diǎn)來(lái)遍歷整個(gè)點(diǎn)雙。

   最后我們只要枚舉 \(u\) 是否選，然后進(jìn)行環(huán)上的 DP 即可。

   void DP(int u,int v) {
   	int F[2] {0,0};
   	for(int w(v); w^u; w=fa[w]) {
   		int G[2] {F[0]+f[w][0],F[1]+f[w][1]};
   		F[0]=max(G[0],G[1]),F[1]=G[0];
   	}
   	f[u][0]+=F[0];
   	F[0]=0,F[1]=-INF;
   	for(int w(v); w^u; w=fa[w]) {
   		int G[2] {F[0]+f[w][0],F[1]+f[w][1]};
   		F[0]=max(G[0],G[1]),F[1]=G[0];
   	}
   	f[u][1]+=F[1];
   }
   

   for(const int &v:g[u])if(fa[v]!=u&&dfn[u]<dfn[v])DP(u,v);
   

void DP(int u,int v) {
	int F[2] {0,0};
	for(int w(v); w^u; w=fa[w]) {
		int G[2] {F[0]+f[w][0],F[1]+f[w][1]};
		F[0]=max(G[0],G[1]),F[1]=G[0];
	}
	f[u][0]+=F[0];
	F[0]=0,F[1]=-INF;
	for(int w(v); w^u; w=fa[w]) {
		int G[2] {F[0]+f[w][0],F[1]+f[w][1]};
		F[0]=max(G[0],G[1]),F[1]=G[0];
	}
	f[u][1]+=F[1];
}

void tarjan(int u) {
	dfn[u]=low[u]=++idx,f[u][0]=0,f[u][1]=1;
	for(const int &v:g[u])if(v^fa[u]) {
		if(!dfn[v]) {
			fa[v]=u,tarjan(v),tomin(low[u],low[v]);
			if(low[v]>dfn[u])f[u][0]+=max(f[v][0],f[v][1]),f[u][1]+=f[v][0];
		} else tomin(low[u],dfn[v]);
	}
	for(const int &v:g[u])if(fa[v]!=u&&dfn[u]<dfn[v])DP(u,v);
}

P4244 [SHOI2008] 仙人掌圖 II

這是一道求仙人掌圖直徑的題目，我們嘗試用一次 DP 的方法求解。

那么思路與上題相似，在樹(shù)邊直接 DP，在葉片上單調(diào)隊(duì)列處理即可。

void Solve(int u,int v) {
	int h(1),t(0),len(0);
	static int q[N<<1],val[N<<1];
	for(int w(v); w^fa[u]; w=fa[w])val[++len]=f[w];
	FOR(i,1,len)val[len+i]=val[i];
	FOR(i,1,len<<1) {
		while(h<=t&&(i-q[h])>(len>>1))++h;
		if(h<=t)tomax(ans,val[i]+i+(val[q[h]]-q[h]));
		while(h<=t&&(val[q[t]]-q[t])<(val[i]-i))--t;
		q[++t]=i;
	}
	FOR(i,1,len)tomax(f[u],val[i]+min(i,len-i));
}

void tarjan(int u) {
	dfn[u]=low[u]=++idx;
	for(const int &v:g[u])if(v^fa[u]) {
		if(!dfn[v]) {
			fa[v]=u,tarjan(v),tomin(low[u],low[v]);
			if(low[v]>dfn[u])tomax(ans,f[u]+f[v]+1),tomax(f[u],f[v]+1);
		} else tomin(low[u],dfn[v]);
	}
	for(const int &v:g[u])if(u!=fa[v]&&dfn[u]<dfn[v])Solve(u,v);
}

P3180 [HAOI2016] 地圖

這道題如果用線段樹(shù)合并，那么離線詢問(wèn)后在 Tarjan 時(shí)直接合并和回答會(huì)節(jié)約很多代碼。

仙人掌上求最短距離

P5236 【模板】靜態(tài)仙人掌

先建出圓方樹(shù)，然后對(duì)于一個(gè)點(diǎn)雙，會(huì)有一個(gè)圓點(diǎn)在圓方樹(shù)上是方點(diǎn)的父節(jié)點(diǎn)，其余都是方點(diǎn)的子節(jié)點(diǎn)，如下圖。

那么我們可以將方點(diǎn)到父節(jié)點(diǎn)的距離賦值為 \(0\)，其余的圓點(diǎn)到方點(diǎn)的權(quán)值都賦為它們?cè)谌~片上到方點(diǎn)父節(jié)點(diǎn)的距離，這個(gè)可以預(yù)處理后 \(O(1)\) 在線查詢。然后我們樹(shù)上前綴和加起來(lái)，得到 \(\{dis_i\}\)。

預(yù)處理之后來(lái)看看查詢：假設(shè)現(xiàn)在查詢的是 \(u,v\) 的距離，求得它們?cè)趫A方樹(shù)上的祖先為 \(pa\)。

1. \(pa\) 為圓點(diǎn)：那么答案就是 \(dis_u+dis_v-2dis_{pa}\)。
2. \(pa\) 為方點(diǎn)，那么 \(u,v\) 同在以 \(pa\) 為方點(diǎn)的點(diǎn)雙上：設(shè) \(su,sv\) 分別為 \(pa\) 的子節(jié)點(diǎn)中最接近 \(u,v\) 的，答案為 \((dis_u-dis_{su})+(dis_v-dis_{sv})+Dis_{pa}(su,sv)\)，\(Dis_{pa}(su,sv)\) 表示在 \(pa\) 這個(gè)點(diǎn)雙上， \(su,sv\) 的最近距離。

1045C - Codeforces

上題的弱化版。雖然不是仙人掌了，但是可以轉(zhuǎn)化成仙人掌的模型。

圓方樹(shù)上計(jì)數(shù)

在圓方樹(shù)上計(jì)數(shù)很容易計(jì)算重復(fù)，有的時(shí)候我們可以運(yùn)用圓點(diǎn)和方點(diǎn)交替出現(xiàn)的性質(zhì)來(lái)求解。

P4630 [APIO2018] 鐵人兩項(xiàng)

明顯地，先對(duì)點(diǎn)雙建出圓方樹(shù)，然后考慮計(jì)數(shù)。

如果我們考慮在方點(diǎn)計(jì)算 \(c\) 處于當(dāng)前點(diǎn)雙時(shí)的所有情況，似乎去重非常麻煩，那怎么辦？我們可以在圓點(diǎn)也計(jì)數(shù)，并從答案中減去計(jì)出的數(shù)，就可以做到容斥去重，這題就變得十分簡(jiǎn)單。

void tarjan(int u,int fa) {
	dfn[u]=low[u]=++idx,siz[st[++top]=u]=-1,++cur;
	EDGE(g,i,u,v)if(v^fa) {
		if(!dfn[v]) {
			tarjan(v,u),tomin(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				siz[++dc]=1,G.att(u,dc,0);
				do ++siz[dc],G.att(dc,st[top],1);
				while(st[top--]^v);
			}
		} else tomin(low[u],dfn[v]);
	}
}

void dfs(int u) {
	Siz[u]=(u<=n);
	EDGE(G,i,u,v)dfs(v),ans+=(ll)2*Siz[u]*Siz[v]*siz[u],Siz[u]+=Siz[v];
	ans+=(ll)2*Siz[u]*(cur-Siz[u])*siz[u];
}

虛仙人掌

其實(shí)就是在圓方樹(shù)上建虛樹(shù)。

P4606 [SDOI2018] 戰(zhàn)略游戲

比較簡(jiǎn)單的計(jì)數(shù)題。

mx的仙人掌

【集訓(xùn)隊(duì)互測(cè)2016】火車(chē)司機(jī)出秦川

點(diǎn)分治

【UR #1】跳蚤國(guó)王下江南 - 題目

點(diǎn)分治配合 FFT，分治中心還要找?guī)?quán)中心。

仙人掌鏈剖分

【清華集訓(xùn)2015】靜態(tài)仙人掌 - 題目

注：這題可以用 bitset 做，更簡(jiǎn)單。

這題將仙人掌上所有點(diǎn)到根的最短和最長(zhǎng)距離都固定，讓你帶修查詢。剖分的重點(diǎn)是把仙人掌上的點(diǎn)（不是圓方樹(shù)上的）分成三類，不過(guò)這個(gè)我們后面會(huì)講。

1. 還是像在樹(shù)上樹(shù)剖一樣在圓方樹(shù)上 DFS 計(jì)算各個(gè)子樹(shù)的大小并找出重兒子。

2. 第二次 DFS，但是與在樹(shù)上樹(shù)剖有很大區(qū)別：

   • 對(duì)于根節(jié)點(diǎn)，它肯定是個(gè)圓點(diǎn)：它的 DFS 序?yàn)?\(1\)，\(top_{rt} = rt\)。
   • 對(duì)于方點(diǎn)：它不計(jì)入 DFS 序，因?yàn)闆](méi)有必要，但是樹(shù)剖的時(shí)候會(huì)把它放進(jìn)去一起剖，這個(gè)不影響復(fù)雜度。同時(shí)它的子節(jié)點(diǎn)的 DFS 序都需要它來(lái)賦，我們按環(huán)上的順序給它的子節(jié)點(diǎn)賦。
   • 對(duì)于非根的圓點(diǎn)，沒(méi)有什么特殊的。

   這些點(diǎn)遍歷子節(jié)點(diǎn)時(shí)都要先遍歷重兒子（如果存在）。

   我們給點(diǎn)分類是在方點(diǎn)給子節(jié)點(diǎn)賦值時(shí)分類：

   0. 根節(jié)點(diǎn)和各個(gè)方點(diǎn)的重兒子都分為 \(0\) 類點(diǎn)。
   1. 對(duì)于一個(gè)方點(diǎn)的所有輕兒子，將重兒子到根節(jié)點(diǎn)最短路徑上的點(diǎn)分為 \(1\) 類點(diǎn)。
   2. 對(duì)于一個(gè)方點(diǎn)的所有輕兒子，將重兒子到根節(jié)點(diǎn)最長(zhǎng)路徑上的點(diǎn)分為 \(2\) 類點(diǎn)。

   然后在修改時(shí)我們把它們分開(kāi)就可以做到不重不漏。

3. 修改，這一步需要的判斷較多：

   對(duì)于 \(u\)，我們?cè)谛薷乃狡滏滍?\(top_u\) 時(shí)要注意：

   1. 如果 \(top_u\) 是根，將它所有種類的點(diǎn)都修改了。

   2. 如果 \(top_u\) 是非根圓點(diǎn)，將它所在的那個(gè)點(diǎn)雙上所經(jīng)過(guò)所有種類的點(diǎn)都修改了。

   3. 最后要判斷 \(u\) 是不是圓點(diǎn)：

      • 是圓點(diǎn)：修改 \(u\) 到鏈頂?shù)淖庸?jié)點(diǎn)。
      • 是方點(diǎn)：修改 \(u\) 的父節(jié)點(diǎn)到鏈頂?shù)淖庸?jié)點(diǎn)。

      修改時(shí)注意修改的點(diǎn)的類型，\(0\) 類點(diǎn)是一定要修改的。

回到本題，修改的信息用線段樹(shù)維護(hù)即可。

具體的還有一些東西需要維護(hù)：提交記錄 #746768 - Universal Online Judge (uoj.ac)。

結(jié)合其他算法

487E - Codeforces

這題可以結(jié)合可刪堆和線段樹(shù)，比較簡(jiǎn)單。

P3180 [HAOI2016] 地圖

這題可以結(jié)合線段樹(shù)合并還有莫隊(duì)。