SPOJ QTREE2 - Query on a tree II

QTREE寫起來

連結：SPOJ QTREE2 - Query on a tree II

又是樹

題目：

給定N-1條邊，邊上有權重，為一棵N個節點的樹，並進行若干操作，如下：

• DIST a b: 詢問從a走到b的距離，距離即走過的邊之權重總和。
• KTH a b c: 詢問從a走到b的路徑裡第c個點編號為何。

做法：

沒有修改，這邊用倍增法做就好。

D[x]: x點的深度，D[root] = 1。

Dist[x]: 從root走到x的距離，D[x] = D[x的父節點] + x與父親的邊權。

求兩點距離部分，在DFS時對每個點順便做好Dist[x]，答案即是Dist[a]+Dist[b]-Dist[lca(a,b)]*2

另一種詢問，可以先求a, b的LCA，可知從a到b共有D[a]+D[b]-D[lca(a,b)]-1個點

先判斷第c個點在a~LCA還是LCA~b，並與a(或b)相隔幾步。

然後用倍增法爬上去，利用稍早求LCA建立好的表格，

如果相隔步數>=2^i，就讓a(或b)走到F[i][a(或b)]，最後就會走到那個點，計算的過程不細說了。

複雜度：倍增法建表O(NlogN)，詢問每次約O(logN)時間可完成。

code: