本文主要介紹袁方圓百度百科(袁方圓百科)，下面一起看看袁方圓百度百科(袁方圓百科)相關資訊。
\(\text{0x00。}\)前言突然發(fā)現(xiàn)整個機房只有我一個人可以 我不知道方樹，最近方樹在模擬游戲中出現(xiàn)的次數(shù)多得驚人，所以我來學習一下。it 這不是因為我能。;草，不要解決問題。
\(\text{0x01。}\)廣義平方樹在平方樹中定義，每個原點對應一個點，每個點對對應一個正方形點；對于每一個點雙連通分量，其對應的正方形點連接到這個點雙連通分量中的每一個點；正方形樹的每條邊連接一個點和一個正方形點。而如果一個點連接多個正方形的點，那么這個點在原圖上的點就是這些點對之間的切點。需要注意的是，正方形樹的點數(shù)小于\(2n\)，受點數(shù)的限制。
\(\text{oi-wiki}\)不應掛斷(
構(gòu)造內(nèi)聯(lián)void添加ge (int u，int v) {e [u]。就位_后退(v)，e [v]。launte _ back(u)；}void tarjan(int u，int fa){ dfn[stk[tp]= u]= low[u]= idx；for(const auto v:e[u])if(v^fa){ if(！dfn[v]) {tarjan(v，u)，low[u]=min(low[u]，low[v])；if(low[v]=dfn[u]) {addedge( cnt，u)；while(stk[tp]^v) addedge(cnt，stk[tp-])；addedge(cnt，stk[tp-])；}} else low[u] = min(low[u]，dfn[v])；} }//留著孤兒沒意義?？靵碜鲱}！例1。\(\text{[apio 2018]馬拉松}\)
題目描述:給一個無向圖，求\((s，c，f)\)三元組的個數(shù)，分別代表從\(s\)出發(fā)，經(jīng)過\(c\)到\(f\)(經(jīng)過點不能重復)。
考慮當(s，f)固定時，有多少——滿足條件。實際上就是建立了平方樹之后\(s，f\)所屬的點對中的點。這從感性的角度來看其實是很有道理的?？紤]一個點double \(b\)和它外面的一個點\(a\)，那么就可以從\(b\)中的任意一點出發(fā)，到\(a\)。法沒有經(jīng)過他去過的地方就回來了。
但是我們?nèi)绾斡嬎阖暙I呢？將正方形點指定為它所代表的點對的大小，將點指定為\(-1\)。如何理解\(-1\)？或者看一張圖:
假設\(s=4，f=5\)，我們可以發(fā)現(xiàn)\(1，2\)是由相鄰的平方點計算兩次，所以需要減去。因為路徑的兩端一定是點，而且點是交錯的，這個東西是對的。
現(xiàn)在問題其實變成了每個點會被路徑計算多少次，樹\(\mathtt{dp}\)就夠了。
例2。\ (\ text {cf487e tours} \)
題目描述:給定一個簡單的無向連通圖，需要兩個操作:
修改點的點權(quán)重；求兩點間所有簡單路徑上點權(quán)的最小值。利用上面的結(jié)論，可以直接維護一個方形點\(\text{multiset}\)來維護對應的點對，然后用樹截面來維護。
問題是當多個點對中包含的切點被修改時(比如菊花圖)，復雜度會直接上升。這里有一個經(jīng)典的\(\rm詭計\):方點不維持父點的權(quán)重，所以點只會修改自己的父點。顯然，只有當\(\rm lca\)是方點時，查詢才會出錯，所以可以補充父 s點正好在頂點。
例3。\(\text{[sdoi 2018] }\)策略游戲
題目描述:給出一個簡單的無向連通圖。有\(zhòng)(q\)個查詢，每次給定一個點集\(s\)，有多少個點\(u\)滿足\(u\notin s\)和刪除\(u\)后\(s\)中的點不都在一個連通分支中。
很容易發(fā)現(xiàn) \(s\)中的點不都在連通分量中等價于s中存在\(u，v\)，使得\(u，v \)之間的所有簡單路徑不連通。所以相對于\(u，v\)，各自點對之間的點就是合法的切割點，然后構(gòu)建一棵圓樹。
那么實際上就是計算樹上\(s\)的中點形成的最小連通塊中的點數(shù)。首先給出計算方法:預處理從根到每個點的點數(shù)\(\rm val\)，按\(\rm dfs\)排序\(s\)。答案是
\ [-| s | [\ text {lca} (s _ 1，s _ { | s | })\ le n]\ frac { 1 } { 2 } \ cdot \ sum _ { i = 1 } { | s | } \ text { val } _{|s| 1}=s_1\)。
給出一個理解方法:在計算\(\rm val\)時，我們把權(quán)重掛在\(u\)和父親這一邊，實際上是在模擬\(\rm dfs\)的過程。每一次相鄰點的匹配，實際上都是走出一個子樹，然后走進一個子樹，最后從最后一個點走回第一個點，然后以\(\text{lca}(s_1，s_{|s|})\)為根做一個\(\rm dfs\)！可以發(fā)現(xiàn)每個點會計算兩次。同時也可以發(fā)現(xiàn)，我們還沒有計算出\(\text{lca}(s_1，s_{|s|})\)的貢獻，所以要特別判斷一下。
例4。\(\text{chef and sad pairs}\)
用顏色來考慮這個問題:如果你建一棵正方形樹，由于點\(x\)而悲傷的對數(shù)相當于在\(x\)(你不妨把你的父親想象成\(x\))的不同子樹中選擇一對點。但是這個\(\rm dfs\)的復雜度是平分的，所以需要建立一個虛擬樹來求解。
但是，仍然有一個問題:對于 祖先-后代amp關系(假設\(u，v\)是同一個顏色，兩者之間沒有其他顏色的點)，這個顏色的統(tǒng)計沒有答案！所以你需要在鏈條上有所作為。好水。
讓 ■放一個代碼:\(\text{submission。}\)
此外，還可以進行啟發(fā)式合并:\(\text{solution。}\)
\(\text{0x02。}\)窄圈樹的定義不是很清楚為什么要分類。
現(xiàn)在無向圖保證是仙人掌森林。仙人掌:每條邊至多屬于一個環(huán)的無向連通圖；可以發(fā)現(xiàn)此時每個點對對應一個簡單的環(huán)，這樣仙人掌問題就可以轉(zhuǎn)化為基環(huán)樹上的問題解，就像這樣:構(gòu)造void tarjan (int u，int fa) {dfn [u] = low [u] = idx，stk[tp]= u；for(const auto v:g[u])if(v^fa){ if(！dfn[v]) {tarjan(v，u)，low[u]=min(low[u]，low[v])；if(low[v]==dfn[u]) /*方邊*/；else if(low[v]dfn[u])/* round edge */；} else low[u] = min(low[u]，dfn[v])；}}快來做題！例1。\(\text{[bzoj 4316] }\) small $\ \rm c\ $獨立集
首先，如果這是一個樹形結(jié)構(gòu)，可以用\(dp(i，0/1)\)來求解?，F(xiàn)在問題轉(zhuǎn)移到仙人掌上了。先建立一個正方形樹，點與點之間的父子關系還是一樣的\(\mathtt{dp}\)，否則我們就處理正方形點的值\(\mathtt{dp}\):由于原來的點對是一個環(huán)，所以\(0/1\)的狀態(tài)實際上是兩個邊界點都沒有選擇。
例2。\(\text{[shoi 2008] }\)仙人掌地圖\(\text{ ii}\)
這個問題是一個巨大的坑:如果你不 t再建一棵樹，那么圓邊就容易被忽略了！記得在圓的邊緣從\(\rm tp\)減去一！
例3。\(\text{[haoi 2016] }\)地圖
首先對問題的含義進行轉(zhuǎn)換，發(fā)現(xiàn)所要求的其實是點\(x\)在正方形樹的子樹中，其油膩度\(\le y\)為奇數(shù)/偶數(shù)的拉面品種。
對于子樹問題，一個角度是\ (\ text {dsuotree/} \)線段樹合并，即直接搞子樹；另一個角度是用\(\rm dfs\) sequence把它變成一個序列問題，這樣就可以用掃描線(這個問題不可以)\(\text{/ }\)之類的算法來阻擋。
讓 讓我們在這里詳細討論一下阻塞法。奇數(shù)/偶數(shù)品嘗時間是很好的統(tǒng)計數(shù)據(jù)，關鍵是如何限制 油膩度 ?？梢韵氲接脴湫螖?shù)組，但是修改復雜度就變成了\(\mathcal o(n\sqrt n\log n)\)的事情。其實可以用range blocking(這是第一次看到qwq)，把\(s(b，0/1)\)定義為權(quán)值屬于出現(xiàn)次數(shù)為偶數(shù)/奇數(shù)的第\(b\)塊的簇的個數(shù)，通過一次修改即可實現(xiàn)\(\mathcal o(1)\)。
我還沒有 我還沒有寫代碼。我 我有時間的時候會寫的。
標簽:
子樹點
了解更多袁方圓百度百科(袁方圓百科)相關內(nèi)容請關注本站點。