樹鏈剖分bzoj

1/3ページ

bzoj 3319: 黑白樹 (並查集)

題目描述 傳送門 題目大意:給定一棵樹,邊的顏色為黑或白,初始時全部為白色。維護兩個操作: 1.查詢u到根路徑上的第一條黑色邊的標號。 2.將u到v 路徑上的所有邊的顏色設為黑色。 Notice:這棵樹的根節點為1 題解 先將所有操作正著進行一遍,將所有的黑邊相鄰的點按照關係合併,就是一個集合中的代 […]

BZOJ 4505 K個串 主席樹標記永久化

Description     兔子們在玩 kk 個串的遊戲。首先,它們拿出了一個長度為 nn 的數字序列,選出其中的一個連續子串,然後統計其子串中所有數字之和(注意這裡重複出現的數字只被統計一次)。     兔子們想知道,在這個數字序列所有連續的子串中,按照以上方式統計其所有數字之和,第 kk 大 […]

樹鏈剖分求LCA(最近公共祖先)

LCA(Lowest Common Ancestor 最近公共祖先)定義如下:在一棵樹中兩個節點的LCA為這兩個節點所有的公共祖先中深度最大的節點。 如圖,節點11與節點6的LCA為節點4,節點12與節點1的LCA為8,節點11與節點10的LCA為10。 現在我們來了解一下LCA我認為最好的演算法: […]

BZOJ 3720 Gty的妹子樹 塊狀樹

題目大意:維護一棵樹,每個點有一個權值,提供下列操作: 1.詢問某棵子樹中有多少個節點的權值大於x 2.修改某個節點的權值 3.增加一個葉子節點 強制線上 傳說中的樹分塊 首先DFS,對於每個節點,如果這個節點的父親節點所在塊未滿,就塞進父節點所在塊中,否則自成一塊,然後與父節點所在的塊連邊 新增節 […]

BZOJ 3720 Gty的妹子樹 樹上分塊

題目大意:給出一棵樹,要求維護:1.求出以x為根節點的子樹的嚴格大於y的數量。 2.將一個節點的權值改變。 3.在一個節點下加一個權值為y的節點。 思路:分塊這個東西太神了(別找我分析時間複雜度。。樹上的分塊更神。。。 首先,分塊的原則和正常分塊一樣,把一棵樹分成√n塊,每一塊不超過√n個,然後所有 […]

[BZOJ 2502]清理雪道:上下界網路流

點選這裡檢視原題 點選這裡檢視上下界網路流教程 這個題很明顯就是: 從ss到所有點連下界00上界infinf的邊(因為可以從任何點出發) 從所有出度為零的點到tt連下界00上界infinf的邊(最優方案一定是到達該點才結束) 所有點向他能到達的點連下界11上界infinf的邊(每條邊至少走一次) 那 […]

bzoj 4155: [Ipsc2015]Humble Captains 最小割 dp

題意 每天下午放學時都有n個zky衝出教室去搞基。搞基的zky們分成兩隊,編號為1的zky是1號隊的首領,編號為2的zky是2號隊的首領。其他的zky可以自由選擇是去1隊還是2隊。 zky們當中有幾對zky是好基友(同一個zky可能在多對“好基友”關係中),如果一對好基友在同一個隊,那麼這個隊的戰鬥 […]