CodeChef November Challenge 2012

Level 1
Coin Flip: 簽到
Delicious Dishes: 簽到
Sridhar Likes Travelling:簽到
Level 2
A Wonderful Chocolate:SCDP + 矩陣
Candy Collecting Game:DP Lucky Balance:組合
Jam Board:並查集 ( 注意卡 scanf()… 使用 getchar() .. .
Level 3
Arithmetic Progressions:鏈表優化暴力 ( 快速 FFT
Martial Arts:費用流 || KM ??
Many Left:卡時 + 啟發式貪心

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

POJ 3237. Tree

Brief description:

動態維護一顆點權樹,要求支持以下操作:

  • INSERT T: 插入、在節點 T 下新增一個節點
  • CUT S T: 切掉、切掉以節點 S 為根的子樹,接到節點 T 上。
  • CHANGE T D: 單點修改、將節點 T 修改為 D。
  • ADD T D: 子樹修改、將以 T 為根的子樹中所有結點增加 D。
  • QMAX T: 子樹最值、詢問以 T 為根的子樹中所有結點的最大權值。
  • QSUM T: 子數和、詢問以 T 為根的子樹中所有結點的權值和。

初始是只有 1 個編號為 1 的節點,權值為 0,對於插入 (INSERT) 操作,結點的權值默認為 0,對於鏈接 (CUT) 操作,如節點 T 在以節點 S 為根的子樹中,則忽略。
(總操作數 < = 200000。。) ゆっくり読んでください …