概念

首先你應(yīng)當(dāng)會(huì)點(diǎn)分樹(shù)。

動(dòng)態(tài)點(diǎn)分樹(shù)可以支持每次加一個(gè)葉子結(jié)點(diǎn)并動(dòng)態(tài)維護(hù)點(diǎn)分樹(shù)結(jié)構(gòu)平衡的數(shù)據(jù)結(jié)構(gòu)。

思路

利用替罪羊樹(shù)的思想，考慮 \(\alpha\) 重構(gòu)。也就是說(shuō)，每加入一個(gè)節(jié)點(diǎn)后，先將其點(diǎn)分樹(shù)上父節(jié)點(diǎn)直接視作這個(gè)父親（顯然合法）并更新到祖先的信息，枚舉其所有祖先，找到深度最低的，滿(mǎn)足子樹(shù)大小超過(guò)了父節(jié)點(diǎn)子樹(shù)大小 \(\alpha\) 倍的子樹(shù)（如果有），并重構(gòu)整棵子樹(shù)。重構(gòu)的話(huà)直接對(duì)整棵子樹(shù)重新跑一遍點(diǎn)分治即可。

同替罪羊樹(shù)思想，\(\alpha\) 大致取 \(0.8\) 可以使總重構(gòu)點(diǎn)數(shù)為 \(n\log n\) 級(jí)別，原理我不太懂，畢竟我不會(huì)替罪羊樹(shù)。qwq

有一些可能有用的實(shí)現(xiàn)細(xì)節(jié)，就是對(duì)每個(gè)點(diǎn)開(kāi)兩個(gè)數(shù)組順次存下他的祖先與到其的距離，重構(gòu)時(shí)對(duì)子樹(shù)內(nèi)每個(gè)點(diǎn)的這個(gè)動(dòng)態(tài)數(shù)組同時(shí)彈出，直到彈出要重構(gòu)的子樹(shù)根節(jié)點(diǎn)為止，那么剩下的就是不用重構(gòu)的祖先。點(diǎn)分治時(shí)把當(dāng)前分治塊內(nèi)所有點(diǎn)推入當(dāng)前分治中心及距離即可。

例題

紫荊花之戀

題解