UVa 12238 – Ants Colony

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3390

最近共同祖先(Lowest Common Ancestor，LCA)定義為在一棵樹上，兩個節點u和v，它們離根節點最遠的也就是深度愈低的共同祖先，只有唯一一個。

這題要求任意兩點間的最短路徑，但是因為N太大，所以Floyd-Warshall最短路徑演算法就沒辦法了，而這題有保證這張圖是一棵樹，因為任一兩點u和v之間的最短路徑，以樹來看一定會經過他們的LCA，所以可以得到u和v最短路徑就是dist(root, u) + dist(root, v) – dist(root, LCA(u,v)) * 2，實際畫畫看很好懂。

Codeforces 500 E. New Year Domino

http://codeforces.com/contest/500/problem/E

 

http://www.cnblogs.com/ACMDoli/articles/4268340.html
這題很多人都用線段樹和一個我沒看過的東東，而官方題解我也還沒完全理解…
但我覺得上面這人的想法很好懂，而且Code又簡單 <(_ _)>

 

而一開始我的寫法會產生一個問題，也就是在算 ans 時， 假設有 A、B 兩骨牌，有可能發生 A 的位置比 B 左邊， 但是倒下來的覆蓋範圍比B還右邊的情況，由於我是從右邊依序算每個骨牌要倒到最後的 cost， 然而骨牌 X 要倒到 Y 的 ans 是 cost[X] – cost[Y]，若 Y 是 B 的話，那就會多減掉。 所以應該要改成 ans = cost[X] – cost[set of Y]，而詢問set的部分就用disjoint set處理。