題目：
給定一棵$n$個點的樹，每條邊都有個長度，然後有$Q$次操作/詢問，每次可以佔領一個點，或是詢問某個點到所有已被佔領的點的距離總和。$n,Q\leq 10^5$。
作法：
這題有兩種作法，第一種作法是用平方分割，因為如果是一次佔領完再全部詢問，那麼我們可以用 DFS $O(n)$ 求出每個點的答案，再$O(1)$回答詢問，詳細作法就不提了。而另外一種作法則是：把所有被佔領的點紀錄下來，每次詢問就直接去詢問給定點和所有被佔領點的距離總和，這樣一次的複雜度會是$O(被佔領點個數\cdot logn)$。於是我們考慮把兩種作法合併，當一個一個佔領點時，如果此時佔領的點還沒有那麼多，則直接用求距離再加起來的作法硬算，而當要硬算的點個數達到某個值（假設為$K$）時，就 DFS 一次把所有點的答案都更新好，這樣在詢問時我們就有了詢問的點到前$K$個被佔領點的距離總和了，剩下的部份就硬算即可。這樣可以得到單次詢問的複雜度為$O(Klogn)$，佔領一個點時因為我們不會 DFS 超過$\frac{Q}{K}$次，因此複雜度會是$O(\frac{Q}{K}n)$。由這兩式就可以知道取$K$讓$QKlogn=\frac{Q}{K}n$會是最好的，移項得$K=\sqrt{\frac{n}{logn}}$，總複雜度為$O(Q\sqrt{nlogn})$。但考試時不知道為什麼怎麼取$K$都TLE，後來乾脆取個$100$還$200$就莫名其妙的過了。
事實上可以做到單次詢問$O(logn)$，用的東西叫重心剖分，他的概念是先對原本的樹取重心，把樹分成很多個子樹，再對這些子樹遞迴下去取重心，並且將原樹的重心和其子樹們的重心連起來，這樣我們就得到了一棵重心樹（重心樹上的邊不一定在原樹上出現，但每個點都出現了），不難證明其深度會是$O(logn)$的（之後稱重心樹上的一個子樹為重心子樹）。因此當詢問一個點$x$的答案時，可以直接沿著重心樹往上走（因此要紀錄好每個點在重心子樹上的父親是誰），並在走的過程維護當前答案等於「$x$到當前重心子樹裡所有已被佔領點的距離總和」，這樣一路走到根就獲得答案了。接下來我們要知道如何維護好答案，記當前重心子樹為$T$，他的根$P$，還有如果只看原樹中這棵重心子樹裡的所有點的話，把$P$拔掉會讓他分成許多（原樹中的）子樹，稱其為$T_1,...,T_r$，並且不妨設$x$落在$T_1$裡面。那麼此時所求答案就必須要增加「$x$到所有$T_2,...,T_r$中被佔領點的距離」。這可以拆成兩部份，因為$x$走到這些點都必須經過$P$，因此如果假設在$T_2,...,T_r$中被佔領的點共有$t$個，那麼就可以把所求改成$t\cdot dist(P,x)+P$到$T_2,...,T_r$中被佔領點的距離總和（其中$dist$ 代表兩點在原樹中的距離）。對於前者，我們可以在預處理時，對於每個重心子樹，把他的根到所有他在重心子樹中的點的（在原樹中的）距離都存起來，這樣就能知道$dist(P,x)$了。再來則是要知道$t$，而這可以用「$T$中的被佔領點數扣掉$T_1$中的被佔領點數」得到，因此只要在多佔領一個點時沿重心樹走上去，維護好每個重心子樹中的被佔領點數就好了。最後則是要知道$P$到$T_2,...,T_r$中所有被佔領點的距離總和，這可以拆成「$P$到$T$中所有被佔領點的距離總和」扣掉「$P$到$T_1$中所有被佔領點的距離總和」，因此也只要在新佔領點時維護好這兩個值就可以了，都是利用到已算好的「重心到其子樹中某個點的距離」。
實作有很多寫法，但大部份都很麻煩，畢竟我們要存$P$的每個子樹的一些資訊，還有$P$到其子樹內每個點的距離。一個比較簡潔的記法是，首先我們先對每個點紀錄他是落在重心樹深度多少的地方，那麼如果我們想要紀錄某個重心$P$到某個點$x$的距離，就把這個值存在$dis[dep[P]][x]$裡面就可以了，其中$dep$代表這個點在重心樹上的深度，不難發現這個存法不會讓兩個要存的東西碰撞。再來也蠻麻煩的則是要存：對於每個重心$P$，紀錄他的每個子樹中被佔領的點離他的距離總和，而這也可以只用一個陣列來存，假設$P$在重心樹上落在$T_1$的子節點為$Q$，那麼就直接把$P$到$T_1$中被佔領點的距離總和存到$Q$的位子就可以了，也不難發現這樣不會碰撞。另外剩下的「$P$這個重心子樹中所有被佔領點到他的距離總和和有幾個被佔領點」當然只要存在$P$的位子就可以了。
code :
