HDU 4010. Query on The Trees

Brief description :

… 動態維護一組森林,要求支持以下操作:

  • Link(a, b) 如果 a,b 不在同一顆子樹中,則通過在 a,b 之間連邊的方式,連接這兩棵子樹。
  • Cut(a, b) 如果 a,b 在同一顆子樹中、且 a != b,則將 a 視為這棵子樹的根之後,切斷 b 與其父親結點的連接。
  • Modify(w, a, b) 如果 a, b 在同一顆子樹中,則將 a, b 之間路徑上所有的點權增加 w。
  • Query(a, b) 如果 a, b 在同一顆子樹中,返回 a, b 之間路徑上點權的最大值。

ゆっくり読んでください …

SPOJ 375. Query on a tree

Brief description :

動態維護樹中兩點之間路徑上邊權的最大值。

Tags: Classical

Analysis :

經典問題.. . 樹鏈剖分 300- 行,3.10+ s
動態樹 150- 行。。。 2.90+ s…

(目前 Yang Zhe 作業里的 全局平衡二叉樹 還不知道怎麼實現。>_<。) 樹鏈剖分(。。過去的寫法。。。3s+-。。。
上面是我最開始時的寫法。。寫的非常小心謹慎。。。上來就分別對結點、邊、路徑各定義了一組結構體。。。(Vertex, Edge, Path … 然後全程指針指來指去。。
點和邊各有一個 host 指針。。(點寄宿在邊上。。邊寄宿在重路徑上。。。
。。路徑的本體是一棵線段樹,(。。為了刷榜還特地寫成了自下向上維護的形式。(因為有剪枝。。。。
。然後記錄其最高點的 Vertex 的指針。。(。head。。(。。跳鏈和詢問的時候計算 offset 都要用到。。。
。。

樹鏈剖分(。。。現在的寫法。。3s+-。。。
.. 只保留的 path 這一個結構體。。直接記錄每個點所在的路徑。。。

External link:

https://www.spoj.pl/problems/QTREE/