BZOJ 4025. 二分圖

BZOJ 4025. 二分圖

DarkBZOJ 傳送門
https://www.cnblogs.com/ZeonfaiHo/p/7502056.html

題意

給定一個 n 個點, m 條邊的無向圖, 每條邊在一定時間範圍內存在. 要你判斷每個時間點這張圖是否為二分圖。(n ≤ 1e5,m≤2e5)

題解

我們可以用 Link-Cut Tree 離線的維護圖的連通性,方法是我們把圖當成樹來處理,維護出路徑上最脆弱的邊(也就是最早消失的邊)即可,當新插入的邊連接的兩個點已經處在一個連通分量時,如果新的邊更加健康,我們就去替換掉那條邊,關於 Link-Cut Ttre 維護路徑最值的操作,參考 HDU 4010

(這好像其實也就是 Link-Cut Tree 最正經的用途之,優化網路流!)

回到這個題,我們只需要再維護一下路徑的 size,判斷一下是否有奇數個點(或者偶數條邊)即可,由於現在考察的對象既有邊又有點,還有換根操作,著實容易寫錯,乾脆的把原圖中的邊也放進 Link-Cut Tree 里去維護。

代碼

BOI 2020

BOI 2020

Day 1

傳送門
HackMD
競プロ日常

Problem A. Colors

題意

互動式問題,給定 n,每次你可以將頭髮染成 1-n 中間的一個數字,如果相鄰兩次的數字差的絕對值 >= C,那麼男朋友會注意,返回 1,否則返回 0。每個顏色只能用一次,用儘可能少的詢問找到 C。

題解

很優雅的倍增構造。

Problem B. Mixture

題意

動態維護若干瓶調味料,每瓶調味料中裝有一定質量的 鹽,胡椒與大蒜 的混合物,給定美食家最喜歡的調味料的組成,每次詢問,可以增加一瓶新的調味料或者刪除一瓶之前添加過的調味料,返回至少需要幾瓶可以混合出美食家最喜歡的口味。

題解

不會。

Problem C. Joker

題意

給定一張有 n 個點 m 條邊的無向圖,每次詢問給出一個區間 [L, R],問是否存在奇環,使得環中不包含區間中的點。

題解

是否存在奇環,等價於二分圖判定。靜態可以 dfs,動態的話可以 dsu,最後外面套一層莫隊演算法即可。

當然也可以直接用 lct!

對於刪除 [l, r] 區間的邊,我們可以用類似破環為鏈的方法,轉化為每次詢問保留 (r, l+m) 區間的邊,顯然邊越少越容易合法,滿足單調性。我們按照時間順序依次插入所有邊,用 double-point 維護出處理到時間 r 時,最大的 l 使得當前的狀態合法即可。這樣就可以貼 BZOJ 4025 的代碼了。

Day 2

傳送門
競プロ日常

Problem A. Graph

題意

給定一個邊被紅、藍染色的無向圖,求一組節點的權值方案,滿足對所有的紅邊,關聯的節點的權值和為 1,對所有的藍邊,權值和為 2,滿足條件的基礎上,最小化所有節點的權值和。

題解

讓人想起了之前 Atcoder 上的一道染色的題。不過這個題是實數。做法是隨便找個點和初始標記一路 dfs 下去把每個節點標記成 ax+b 的形式,其中 a 屬於集合 {-1, 0, 1},x 是一個待定係數,最後算出 x 的值即可,需要一些 insight。

Problem B. Village

題意

給定一個樹,求兩組錯位排列的方案 P,分別使得 \sum dist(i, P[i]) 的權值和最大和最小。

題解

首先最小的話顯然儘可能交換相鄰的結點編號就好了,我們就每次找葉子,如果沒有交換過,就和父節點交換,這樣最後有可能還剩一個,沒關係隨便找一個相鄰結點再交換一次就好。

對於最大的情況,我們考察每條邊 (u,v),那麼這條邊貢獻的上界是 min(sz[u], sz[v]),我們發現可以構造方案讓所有邊的上界都達到,方法是只要考察重心,讓每個點都標記在另一顆子樹中即可。

這樣看的話,似乎是需要找一下重心的。。。但是 最快的提交代碼 直接就上了。。只要證明這樣構造之後,可以找到一個節點作為根,使得每個節點都不落入同一子樹中就行了。。而這是顯然的,因為以重心分割的話,子樹的 size 不會超過 n/2。

Problem C. Viruses

題意

基因序列是一個由 n 種數字形成的字元串,其中 0、1 為終止字元,其他為病毒字元,給定一張基因突變的表格,每個表格表示一個病毒字元可能會突變成的基因串,一個基因序列每一秒中,會有一個病毒字元突變,一些病毒字元可能有多種突變方向。給定一些模式串作為抗體,問每個病毒字元所能形成的最短的,不被任意一個抗體所識別的終止序列的長度(或者輸出不存在)。

題解

沒有病毒串的時候顯然可以用類似最短路的方法 dp 出最短長度。。有病毒串的時候開個自動機就好。。由於我們需要支持合併字元串的操作,所以 dp 狀態需要加維,記錄在自動機中的狀態區間,具體說來就是 dp[i][st][ed] 表示基因 i 展開之後,從狀態 st 到狀態 ed 的最短路徑長度。

沖了一發 果斷 TLE 了。雖然本質上是最短路模型,但是本題的邊是廣義的,可能會與多個節點關聯,Dijkstra 著實不太好寫,所以用了 Bellman_Ford,考慮到瓶頸主要在鬆弛(Relax)操作上(每次都要跑一遍神似 Floyd 的 DP),感覺改成 SPFA 可過。

換了 SPFA 之後還是有一個點過不去,看來本題數據還是很良心的。。

看了一下其他人的搞法,最快的 WZYYN 同學非常厲害,直接 Bellman_Ford 加了一個奇怪的剪枝就過了,然後 duality 看起來是常規的 SPFA,在 Relax 的時候跳過了無窮的情況,原理就跟一些矩陣乘法的題目,需要優化掉內層循環的取模差不多。

然後 BenQjiangly 的給都是 Dijkstra 正解。最猛的是 liouzhou_101,直接卡時,居然還卡過去了 Orz。。。(所以我也卡時吧。。> <。。。

BZOJ 2125: 最短路

BZOJ | Luogu
https://cmxrynp.github.io/2018/10/29/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF/
https://blog.csdn.net/LPA20020220/article/details/88887231

題意

給你一個有 n 個點和 m 條邊的仙人掌圖,和 q 組詢問,
每次詢問兩個點之間的最短路。

題解

圓方樹

const int N = int(2e4) + 9, LV = 15;

VII adj[N], adjj[N];
int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;

inline int move_up(int x, int t){
for (int lv=0;t;++lv,t&gt;&gt;=1)
if (t&amp;1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}
void getLCA(int x, int y, int &amp;a, int &amp;b, int &amp;z) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
a = x; b = y; z = fa[0][x];
}

void add_edge(int u, int v, LL w) {
adjj[u].PB(MP(v, w));
}

#define v it-&gt;fi
#define w it-&gt;se
void tarjan(int u = 1, int p = -1) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
ECH(it, adj[u]) if (v != p) {
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
} else if (dfn[v] &lt; dfn[u]) { // find circle
            checkMin(low[u], dfn[v]);
            add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
            for (int i=top;sta[i]!=v;--i) {
                int d = D[sta[i]]-D[v];
                add_edge(nn, sta[i], min(d, L[nn]-d));
            }
        }
    }
    --top;
}
#define p fa[0][u]
void dfs(int u = 1) {
    ECH(it, adjj[u]) {
        dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
        fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
        dfs(v);
    }
}
#undef p
#undef w
#undef v

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int Q, m; RD(n, m, Q);

    DO(m) {
        int x, y, w; RD(x, y, w);
        adj[x].PB(MP(y, w));
        adj[y].PB(MP(x, w));
    }

    nn = n; tarjan(); dfs();

    DO(Q) {
        int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

        //cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;

        if (z &lt;= n) { // round one ...
            OT(DD[x]+DD[y]-DD[z]*2);
        } else { // square one ...
            int d = abs(D[a]-D[b]);
            OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
        }
    }
}

動態仙人掌

https://www.luogu.com.cn/record/31868182

論自殺

論自殺

最近確實有點快要支撐不下去了的意思呢 … 明明自己前幾天自己還在勸說兔子要好好活下去來著?最直接的理由自然還是 公司的事情,我已經被逼到懸崖邊上了。。。沒有公章一大堆公司的合同(員工入職,辦公室更換)現在都處理不了,因為回不了國收不到法人的電話,公司賬戶還有隨時被凍結的危險,這個理由很難理解嗎?本來創業就已經是困難重重的事情,就算大家都齊心協力,也不一定會取得結果。。。但是我實在接受不了因為這樣的原因而結束。。沒人指望你輸出,至少不要扯我們的後腿吧?。。。為什麼要給大家添麻煩呢?,,,每次想找 T 好好討論解決事情,但是人家根本就不想理你,說多了就變成了「瘋狂騷擾」和「瘋狂污衊」。。。就應該被打斷腿。。。這還是隔著幾層屏幕討論事情的結果。。更不用想像見面討論會是怎樣的場面了。。。我到現在都依然沒有理解,,,就算想要開啟新的生活,,,不是應該把公章的事情一次性解決掉才更好嗎?。。。或者交給任何其他人也都可以,,,為什麼一定要把我逼到如此絕境?。。。。。我真的做了什麼十惡不赦的事情嗎?。明明我每次遇到問題都是一再退讓的啊。。。。

前幾天一個人在洛杉磯機場的時候,在看到自己的航班再一次的被取消之後,一個人推著滿載三個行李箱大小的手推車,尋思著接下來去哪裡的時候,孤獨和無助感瞬間縈繞全身,明明有那麼多不得不回去的理由的。。事實上我的航班前一天和後一天都有出發的。。。只能怪自己運氣不好。。。繼續在機場逗留。。還會讓自己過多的暴露在病毒之下。。。我還沒有醫保。。。一旦中招,孤獨的客死他鄉都是完全有可能的。。。

。後來我還找兔子認真的討論了「自殺」這件事情。。。我當時只是覺得,如果真的要「自殺」的話,應該怎麼做都會成功吧。。最簡單的方法可能是,找個高樓大廈,忘記一切,跳下去就好。。。而且在都市圈的話,卧軌應該也是很多人的一個選擇。。不過兔子說,那樣會麻煩到其他人。。打掃起來很不方便,燒炭的話,如果失敗會變成植物人。。。(所以果然還是「靜脈注射氯化鋇」最好?。。。)。。

不過我想真的要是絕望到需要尋死的地步。。。那個時候,我還能為其他人思考這麼多嗎。。。?。。再說 每年身邊自殺的 mtf 那麼多,多死一兩個。。。應該沒有什麼人會在意吧?。。。

分類

先看看 Wikipedia 上怎麼說。。。

在動機上主要可分為兩種:
– 主動型自殺,為達成個人因素以外的目的而進行的自殺。例如,自殺攻擊是為達到某種目的而自殺。(E.g. 三島由紀夫)
– 被動型自殺,僅個人因素導致的自殺。比如逃離性自殺,例如社會壓力而產生心理疾病、藥物、醉酒、物質濫用等,是外因導致其自殺。(E.g. 阿蘭圖靈)

一般來說,主動者受時空背景影響至甚。相較於主動者,被動者在自殺意念發生時,呈現較明顯的低自尊與負向思維傾向。缺乏自信的人較可能發生被動型自殺,憂鬱症患者的自殺幾乎全屬被動型。

文明發展愈高的地區,對社會的不滿愈少,故被動型的比率愈高。

在行為模式上的類型有:
– 安樂死:個體以藉助他人幫助的形式來完成自己的自殺。
– 謀殺自殺:一個人用謀殺的方式,讓另一個人或幾個人在他本人之前或同時死去。
– 相約自殺:兩個或兩個以上的個體之間立下協定,通常是因個人原因,同時或先後自殺。
– 集體自殺:集體自殺指一群人為了同一目的而自殺或互相殺害,而這通常與真實或意識到的迫害有關。(代表作,亂步奇譚)

主動型自殺

  • 自殺式襲擊:犧牲自己以完成攻擊目的。如神風特攻隊、恐怖攻擊中的自殺炸彈客。
  • 政治目的性自殺:為傳達某種理念而自殺,例如死諫、殉情或以死明志,例如在某重要地標自焚。此類自殺亦常見要求他人協助完成者。如2019年自殺的香港反對修訂逃犯條例示威者、鄭南榕。

被動型自殺

  • 脅迫性自殺:為了控制他人(罪惡感、恐懼)而自殺。因認為自己遭到某人惡意待遇(因動機來自感受到他人惡意,故列為被動型),而以死的方式作為報復手段。某些地方文化認為人死後產生的鬼可代為復仇,亦屬這一類。
  • 責任性自殺:為了顯示責任心而自殺,如早期日本在戰敗時的切腹自殺(因具備文化因素,亦含主動性成分)。在現代,此類自殺常見於強迫性格傾向者。(E.g. 如最近負責日本武漢撤僑的首相官邸官員)
  • 逃離性自殺:為了躲避某種事物(如惡疾、痛苦、恐慌、空虛等感受),或是被某事逼迫(如被逼債、畏罪、政權垮台),因而自殺。(大部分情況)

所以我這種大概屬於逃離性自殺了。。我確實不知道該怎麼走出現在的困境了。

方式

「還有什麼比創作出來的故事更真實的呢?」
—— 【剩餘榨值023】在巨大的 shock 後,我們所思考的、所做的一切都將與此有關 34:00

介於 推上的投票給的選項太少了。。這裡重新羅列一下。。大概我能想到的。。包括真實的和虛構的作品:

墜樓

作品:夢日記(附窗子)、亂步奇譚(小林),返校(方芮欣),神鵰俠侶(楊過*)、天使不在 12 月(雪緒)、大時代、聖人大盜

おやすみ世界 #ゆめにっき16周年

夢日記

。。自殺自然是十分誘人的… 所有描繪自殺的作品裡。。最令人印象深刻的自然還是《夢日記》。在夢中辛苦遊歷收集了所有十二扇門的世界。最後的最後。。居然是選擇結束了自己的生命。。。留給玩家無限多的想像空間。。。

亂步奇譚

亂步奇譚的結尾也是關於自殺的描寫,而且還是「集體自殺」,所不同的是,在最後的關頭,小林被班長救了下來。。。從而達成了一個 Happy Ending。。看完最後一集才意識到其實這個結局其實早在 ED 的 PV 里就已經暗示給讀者了。。。多米諾骨牌暗示著「集體自殺」,而最後這個畫面暗示了小林被救下。。。

返校

關於,方芮欣是跳樓還是上吊而死的似乎坊間還有 一些爭議

在返校的開場就可以看見一個彷彿女主自己身影的幻想從樓上跳下去,在加上仲庭的手札,有寫「那人一躍而去,就此離開人世,未曾留下隻字片語。」,推斷方芮欣應該是跳樓而死。雖然遊戲後段 Bad End 的地方又有多處關於上吊的描寫,大概這只是一種贖罪的意象。

自刎

哪吒《哪吒鬧海》、虞姬、項羽《霸王別姬》、黃得功《桃花扇》

哪吒鬧海

哪個 mtf 小時候沒有一個反覆出現的剔骨還父的夢呢?(當然,家長黨就當我沒說。。)。。。出處就是這裡。。(使得在很長一段時間裡,我甚至認為中國人的自殺等價於自刎。。。日本人的自殺等價於剖腹。。。)。。。

私以為,哪吒人生的高光時刻就在於拔劍自刎的那一瞬間(如同孫悟空的高光時刻約等於大鬧天宮時把玉皇大帝打到桌肚下面一樣。。)。。

爹爹,我一人做事一人當,你的骨肉我還給你,我不連累你!

遺憾的是。。這麼一個重要的意象。。。在最近的所有關於哪吒的作品裡。。都被有意識或者無意識的削弱或忘卻了。。。

霸王別姬

再然後自然就是《霸王別姬》了。。。就是大家語文課都學過的那篇課文。。。

「吾聞漢購我頭千金,邑萬戶,吾為若德。」
—— 《史記 項羽本紀》

當然覺得項羽你是不是傻啊。。回去切一下假腿。。再來過就是了。。
而且臨死之前還送人頭給人家發育。。。

生當作人傑,死亦為鬼雄。
至今思項羽,不肯過江東
—— 李清照《夏日絕句》

後來隨著閱歷的增長。。多少稍微能理解李清照這首詩歌的含義了。。。
這種境界果然不是劉邦什麼的可以比的。。。。

「漢兵已略地,四面楚歌聲。大王意氣盡,賤妾何聊生!」

再然後就是回到《霸王別姬》里程蝶衣和袁四爺舞劍這一段,我的理解是如果袁四爺這一秒沒有制止的話,程蝶衣絕對會因為入戲太深而刺下去。(因為下一個畫面所流的眼淚沾濕了妝容。。。)。。

最近又讀了一遍《伶人往事》,裡面程硯秋後來對戲劇的態度,書中寫到:

「我們演一個劇,第一要自己懂得這個劇的意義,第二要明白觀眾對於這個戲的感情……還有人以為戲劇是用來開心取樂的,以為是玩意兒,其實不然」,「一個戲總有它的意義,算起總賬來,就是一切戲劇都有提高人類生活目標的意義」

很多作品裡都有這種戲裡戲外互相映射的設定,如「庄生曉夢迷蝴蝶」之感。例如《霸王別姬》里程蝶衣《思凡》預示性別認同障礙,小賴子唱《夜奔》預示著他會逃齣戲班。紅樓夢第十八回「賈元春歸省慶元宵」所點的四齣折子戲,也全部都是暗示了相關人物的命運,「所點之戲劇伏四事,乃通部書之大過節、大關鍵。」

自縊

作品:亞倫·斯沃茨、打工戰士《Steins;Gate》菊仙《霸王別姬》、Sayori《Doki Doki Literature Club! ?》

互聯網之子

前段時間在推上寫 亞倫·斯沃茨、愛德華·斯諾登、朱利安·阿桑奇和中本聰 的時候,回去重新看了一遍《互聯網之子》,顯然,至親至愛之人的背叛是壓垮亞倫的最後一根稻草。當然現在誰都沒有辦法還原出當時事件的完整情況了。。。

霸王別姬

因至親至愛之人的背叛,在文革中自縊而死的人,應該不在少數吧。。。

Steins;Gate

TBD

Doki Doki Literature Club! ?

TBD

沉江

作品:屈原、桃花扇(史可法)、紅樓夢(林黛玉)

屈原可以算是沉江的鼻祖了吧。。小時候看過《上下五千年》好像留有了一個殘存的印象。。已經不真切了。。。。最近看到的應該還是《桃花扇》。。。有一段關於史可法沉江的描寫(明明你好不容易才殺出重圍不是嗎?。。)。。。齣目名就叫做《沈江》。。。

「俺史可法亡國罪臣,那容的冠裳而去。」
「你看茫茫世界,留著俺史可法何處安放。累死英雄,到此日看江山換主,無可留戀。」

。。。

這種大概也是符合我的美學的自殺方式。。。最好還是海葬。。。

我希望可以死在大海里。。。
溺水而死。。。。
畢竟是島嘛。。。
回歸地球🌍母親的懷抱。。。
—— 小島 みなこ, [Jul 10, 2020 at 7:25:44 PM]

服毒

作品:模仿遊戲(圖靈)、蘇菲的世界(蘇格拉底)、t(逆轉裁判)

飲彈

作品:雲圖(羅伯特)、最後生還者(亨利)、不要和陌生人說話(馮遠征)

雲圖


雲圖你的音樂家,在把他的重要之物(物理學家的馬甲)當出去的時候,就已經有下定決心要輕生的念頭了吧,大家在自殺之前,都會先把自己的重要之物,轉交出去,如果還有的話。。。可是他尋死之前還是做了最後一件事情。。。就是把雲圖六重奏給完成。。。這樣大概也是死的沒有遺憾了。。。

最後生還者

黑人兄弟的死 是《美末》里非常棒的一段演出,完美的渲染出了末世的感覺,這種弄出一對鏡像視角先死一遍從而醞釀壓迫感的手法,在粉粉粉粉粉的《救了個命》的開場也有使用。特別是亨利的死,前一秒還拿著槍對著喬爾,後一秒突然就舉槍自盡,非常的突然。。。

不知為何,這一季的編劇為什麼看起來智商掉線了,我打算等雲完之後再來好好談談《美末2》。。。。

割腕

作品:unlight(雪莉)

卧軌

作品:安娜卡列尼娜

燒炭

作品:???

觸電

生死觀

子曰:「未知生,焉知死」。

記得以前玩《軒轅劍雲與山得彼端》調查墓碑旁邊的人,他會:

「人死之後,葬在地下,佔得多少土地?」

所以墓碑的話,還是留在線上好了,參見 People Die, but Long Live GitHub

而那一處墓碑上面寫著。。。

「墳中安葬著丟番圖。上帝給予的童年佔六分之一,又過十二分之一,兩頰長胡,再過七分之一,點燃起結婚的蠟燭。五年之後天賜貴子,可憐遲到的寧馨兒,享年僅及其父之半,便進入冰冷的墓。悲傷只有用數論的研究去彌補,又過四年,他也走完了人生的旅途。」

我好喜歡這種生死觀…。舉重若輕,等到死亡真正降臨的時候。。面對死神略帶著一點玩笑和調侃。。還留下了一道題目。。給晚輩們以啟發。。
(類似的還有最近的 「Flight recorder inventor: Do Not Open」

而最糟糕的大概是讓遺體住在水晶棺材裡。。。
靈魂永遠得不到安寧。。。

未竟之事

TBD

SPOJ CAKE3. Delicious Cake

Vjudge | SPOJ | TG

先複習一下 插頭 dp 大字典。本題顯然使用染色模型。輪廓線上只有 m 個位置,而且不需要 roll() 操作(不過生成的新插頭,要求前面的區分開來,所以我們還是用 m+1 來標記)。這樣搞得話,2×2 我們會算出答案等於 14,仔細觀察,是因為我們多算了下面兩種不合法的情況。

我們發現這類情況都是因為在前面的轉移中產生了刻痕,而使得後續的插頭合併不合法,需要進一步編碼。
我們可以給每個連通塊強行上一個顏色,不相同的顏色不可合併。但是因為原問題沒有顏色,這樣計數起來會比較麻煩(需要最小染色,並且必須保證相同顏色的連通塊必被合併)。
我們也可以暴力記錄 C(5,2) 個連通塊之間是否產生過刻痕,這樣合併的時候直接判斷即可。

刻痕的維護,首先每次狀態轉移,當前插頭都需要和相鄰兩個插頭(左插頭和上插頭)都標記刻痕。
其次,因為我們使用了最小表示,連通塊的記號會被 relable,因而編碼的時候也需要重新映射。
最後插頭合併的時候,刻痕信息也需要合併。

最後上一下高精度模板就好了。留個 OEIS 地址方便大家 debug。

UOJ 87. mx 的仙人掌

參考資料

官方題解
https://blog.bill.moe/uoj87-mxcactus/

題意

給定一個仙人掌,每次從中選取幾個關鍵節點,求它們之間兩兩之間距離的最大值。

題解

對於樹的情況,如果你只會虛樹或者樹分治,對於仙人掌你肯定也只能這麼做了。
—— 官方題解

所以這個題乃會幾種做法,取決於樹的版本的那個問題,你會幾種做法。官方題解 的六、七、八、九,提供了四種思路。這裡先實現第一個演算法 —— 虛仙人掌。

虛樹

先當成樹做,拿個 30 分再說。。。這裡我用 f[] 數組記錄向下的最長距離,然後在更新 f[u] 之前,先用 f[v] 和 f[u] 一起更新一下全局的直徑,這樣就不需要記錄次大值了!

http://uoj.ac/submission/387435

虛仙人掌 (a.k.a. 圓方樹)

首先對這類題目來說,通常的做法,是 dfs 的時候,找到環,然後再環上手工 dp 一次(但其實我總是敲錯,需要依靠底力),把經過環的結果統計到答案,並更新到環上的根節點。
事實上對於 BZOJ 1023. [SHOI2008]cactus仙人掌圖IOI 2008 D2T1 Islands 我們就是這樣做的(分別是 直徑 和 最長鏈,轉移方程幾乎一樣)。

但我們發現並不是總能靠底力凹出來,比如 BZOJ 2125: 最短路,樹上兩點的最短路需要求 lca,仙人掌上怎麼求 lca,似乎需要大量 if-else 判斷 = =!!!
這個題的情況類似,因為在構建虛樹的過程中,我們也需要求 lca。

這個時候我們就需要使用一種 常用的技巧 圓方樹。參見 圓方樹——處理仙人掌的利器

簡單說來,圓方樹就是把環邊都去掉,新建一個 方點 來代替這個環,用環上的根節點連一條邊到她,在從她到每個環上的其他節點連一條邊,形成菊花形狀以拆環為樹(怎麼樣?是不是很像 block-cut tree)。

具體實作的話,先建三個結構體,分表表示 —— 原圖,圓方樹,虛樹。分別記作 G,C,T。求圓方樹的過程,可以類比 tarjan 求雙聯通分量,我這邊是在最深的節點拉回反向邊的時候,把環摳出來的(因而需要取個反)。
這裡連向方點的權值為 0,而從方點連出的邊的權值為左右兩條路徑的長度取 min。

緊接著在 C 上再 dfs 一次,預處理出 dp 和 lca 所需要的信息,為構造虛樹做準備。最後求虛樹的地方,和 之前寫的代碼 唯一的不同,是如果是從方點連出去的邊,需要把這個環上連出去的那個孩子也加到樹中,因為我們需要這些節點來正確處理環上的 DP。

void add_edge(int x, int y) {
if (x &gt; G.n &amp;&amp; x != C.fa[0][y]) { // 如果是從方點連出去,並且 y 不是連出去的那個孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
adj[x].PB(z);
x = z;
}
adj[x].PB(y);
}

這個地方也是之前裸凹的時候最麻煩的地方,因為現在有了圓方樹,所以幾行就處理了掉了w。

接下來是下一個容易錯的地方,以樣例來說,在建立虛樹的時候我們會把 2 和 9 所在的這個環也加到虛樹里,而這個環本身的信息有可能會節外生枝,包含一些本不應該被考慮到節點(這裡是 7),所以我們更新答案的時候乾脆只用圓點的信息更新即可(上面 add_edge 里補上的節點並不會影響)。

參見 下圖

最後說一個讓我 wa 成傻逼的地方,就是最後的資源回收。。。因為這種虛樹的題通常我們是不能無腦 memset 的,但是我們剛才構建虛樹的時候,中間又加入了一些新的節點,所以直接 for 循環那個數組的話會錯。。
所以,最好在遍歷樹結束的同時把這些不用的信息都清理掉。。。

http://uoj.ac/submission/387655