集訓隊作業(yè)query on a treespoj375解題報告

1、tree（spoj375摘O(nlogn+O(nlogn+問題簡有一棵 n 個節(jié)點的樹，并且把它的 n-1 條邊編號為 1,2,3,n-1。你的程序要能執(zhí)行以下CHANGEitiiQUERYabab的路徑上邊權(quán)最大的邊的權(quán)值。10000，但是操作數(shù)會很多。分算法p，我們可以：p上某一段的權(quán)值和，以及最大/pppppp 向靠近根的方向延長（splice 操作p 尾部節(jié)點的父親向下的邊設(shè)p p。pspliceu到根的路徑上的邊全部設(shè)為實邊（expose操作u 所在的路splice 操作即可。2求兩個節(jié)點u,v 的最近公共祖先：不妨設(shè)u 的深度較大u 執(zhí)行expose 操作。如 v 執(zhí)行的過程中記錄

2、最早的剛被expose (u)時遍歷到的點par，這就是u v 的最求節(jié)點 u 到其祖先 par 路徑上的最大的邊的權(quán)值：把節(jié)點 u 到根的路徑上的邊全部1。u,v5u,v 的最par6。以上操作，也可以用路徑操作在平均對數(shù)時間內(nèi)完成147O(nlogn + qlogn)的算法O(logn)的時uu 某些邊不屬于任何一條路徑，稱之為獨立邊。我們用線段樹維護每條路徑。應(yīng)的線段樹中做維護。前者復雜度 O(1)；后者復雜度為 O(logm)，其中 m 為邊 i 所在的路徑m n；對于QUERY 操作，先求出節(jié)點u 和節(jié)點v 的最近公共祖先par，然后分別求u par的最大邊權(quán)值與v par 的最大邊

3、權(quán)值，最后取兩者的最大值。求某個點u 與其par 之QUERY引理 1按照以上貪心思想對任意一棵 n 個節(jié)點的樹進行路徑剖分，任意點 u 到其任意par O(n0.5)條。證明定義一個集合S，它的元素是u par 之間所有的邊。設(shè)S 中的邊屬于k 條路徑和獨立邊，這些路徑和獨立邊之間的分界點為p1, p2, pk ，其中pkpar。那么p1 必然連接S1p2也必然連S2 pkS k par 1 由于跟本題的解答無關(guān)，以上忽略了許多動態(tài)樹的其他功能。如果您對它們感興趣，或者想進一步了解對復雜度的分析，請參見Network Flows: Theory, Algorithms, and Applic

4、ations 2 123.k 1k k k(k 2k(k 條邊。顯然2最大為 n-1 ，這時k 8n13 O(n0.52定理 1理論上 QUERY 操作的時間復雜度最多為 O(n0.5logn)證明根據(jù)引理1，我們知道一次 QUERY 操作最多訪問 O(n0.5)條路徑和獨立邊，而 O(n0.5logn)QUERY QUERY操作的復雜度就是 1是算法一和算法二實際運行時間的比較表 數(shù)據(jù)編號及說明QTREE1.i（樹的形狀隨機CHANGE 操作與QUERY 操作之比為QTREE2.i（樹的形狀隨機CHANGE 操作與QUERY 操作之比為QTREE3.i（樹的形狀隨機CHANGE 操作與QUERY 操作之比為QTREE4.i（一條鏈的情況CHANGE 操作與QUERY 操作之比為QTREE5.i（一條鏈的情況CHANGE 操作與QUERY 操作之比為QTREE6.i（一條鏈的情況CHANGE 操作與QUERY 操作之比為1小本題是 spoj 上的難題，在筆者之前僅有四人 AC。本文算法的核心思想都是用路徑剖