Problem#
給你一個有 $n$ 個點的無向圖，另外給你一個整數 ss。
定義點 a 與點 b 之間是否是透過點 c 連接的，必須符合以下條件:
- 其中 $a < c$ 且
a,b,c互不相等 - 從
c到a的路徑長可以被ss整除 - 從
c到b的路徑長可以被ss整除 - 從
c到b的路徑不能和從c到a的路徑重疊
要你回傳一個陣列 count 其中 count[i] 代表透過點 i 連接的 (a, b) 有幾組
測資限制#
- $2 \le n \le 1000$
- $0 \le a_i, b_i \le n$
- $1 \le w_i \le 10^6$
- $1 \le ss \le 10^6$
- $\text{edges} = n-1$
想法#
- naive: 枚舉
a,b,c直接去找符合規則的數量有多少個 $O(n^3)$ -> TLE
枚舉每個點 $i = [0, n-1]$ 當起點，如果點 $i$ 是中間點(c)點時，其所有子樹所符合規則的節點個數可能是: $ch_0, ch_1, ch_2, \dots$，而總共存在幾組就要去算這幾個子樹的相連情況: 可以是 $O(n^2)$ 去相乘並加起來，例如: ch0 * ch1 + ch0 * ch2 + ch1 * ch2，但是這樣還是會 TLE。
這邊可以採取一個較好的方法是: 累計目前符合規則的節點數量總共多少(node)，對於新加入的子樹來說(其符合規則的節點數量是 ch)，會多了 node * ch 種相連的方法，接著累加節點數量(node += ch)，這樣一來只要遍歷一次子樹的節點個數($ch_0, ch_1, ch_2, \dots$)，掃一次 $O(n)$ 邊走邊累加總共有多少種方法，即是 connect[i] 的答案。
以點 0 為例，它有兩個子樹，往 6 和往 3，其中往 6 的子樹有 2 個點符合規則，往 3 的子樹有 1 個點符合規則，那則代表存在 $2 \times 1 = 2$ 個以 0 為中間點的路經。
如何用程式找一個子樹有幾個符合規則的節點? DFS 去往下遍歷，並累積路徑長，當符合規則時便可以 $+1$ 去統計這個子樹總共有多少個節點符合規則。
AC Code#
- 時間複雜度: $\mathcal{O}(n^2)$
- 空間複雜度: $\mathcal{O}(n)$
心得#
一開始和朋友一起寫，想成用 floyd warshall 然後去看存不存在符合規則的點 c 然後統計數量，但因為是 $O(n^3)$ 所以當然 TLE QQ。
後來有想到用 DFS ，但卡在實作細節，和最後求出所有子樹的答案後，要如何算出所有路徑時，$O(n^2)$ 還是會 TLE，後來是看了其他人的題解才寫出來QQ