POJ 1741 Tree

男人八題之一

Problem

Given 一 undirected weighted tree, 問有多少 pair vertices (u, v) 的 distance ≤ k
|V| ≤ 10000

Solution

這題是經典的 divide and conquer on tree

假設現在的 root 為 x, 可以把 path 分為 2 類: 經過 x 和不過經過 x 的
現在先數經過 x 的
如果 (u, v) 是經過 x 的 path, u 和 v 一定來自 x 的不同 subtree
所以先對 x 的每棵 subtree 做一次 traverse, 取得每個 vertex 和 x 的 distance

但是目標這步要 linear
具題方法是先 traverse subtree 1, 取得 dist1[]
然後 traverse subtree 2, 取得 dist2[]
對這2條array做一次sliding window, 就計到所要的 pair
然後把 dist1[] 和 dist2[] merge 起, 如此類推

之後就要數不經過 x 的
那些 path 是獨立在 x 的 subtree 的
這步就是做 divide 了!
把 x remove, 然後 recursive 對 x 的 subtree 再數

但這樣 worst case是 O(N²)的
目標是要使得每次 divide 後每棵 subtree 的 size 盡量接近
這就要搵 CG of tree

CG of tree 的定義是 delete 該 vertex 後, 所形成的 component size 不大於 n/2 , n = tree size
又是可以做一次 traverse 找到
數學上證明了總時間複雜度為 O(N lg²N)