0w1

Centroid Decomposition

CFR 790 B. Bear and Tree Jumps ( Centroid Decomposition, Divide and Conquer )

Problem - B - Codeforces題意: 給一棵邊權為 1 的樹,問所有有序點對的距離總和。資料規模: N ≤ 2e5 K ≤ 5 TL : 2000 ms解法: 考慮樹分治,分治後都是一個子問題。分別結算子樹本身的貢獻後,計算每個需要經過當前這個重心的點對的貢獻,以及以當前這個…