樹分治

點分治

應用：

樹上所有路徑統計
樹上每個節點做根，信息統計。

注意：需要在求出重心后重新統計子樹大小，別寫假了。

還有就是一般點分治用于子樹內 $O(size)$ 信息的合并，如果子樹內只貢獻 $O(1)$ 個信息，那么可以直接將信息放到狀態中作樹形 dp。參考 P2634 [國家集訓隊] 聰聰可可

P3085 [USACO13OPEN] Yin and Yang G

將兩種顏色邊權分別設置為 $-1$ 和 $1$，轉化為三段路徑和為 $0$。如果統計中間的那個點和另一個端點的話需要用到乘法原理，有些麻煩而且無法排除同一端點不同中點的情況。

可以對于端點分類：祖先有可以做中點的點和祖先沒有可以做中點的點，然后分來統計即可。

P4886 快遞員

思路新奇的題目，如果枚舉所有點做根，然后統計是 $O(n^2)$ 的。

可是我們發現其實可以縮減計算量，假設當前以 $c$ 為根，存在一個組 $(u_i,v_i)$ 使得兩者是最長路徑且經過 $c$，或者存在至少兩組 $(u_i,v_i)$ 使得 $u_i$ 和 $v_i$ 在同一子樹內，且兩組點對不同子樹。這樣子就無法縮減答案了，否則進入那顆包含最大 $(u_i,v_i)$ 的子樹。

借鑒點分治思想，每次選取子樹內重心去跳，復雜度是 $O(n\log n)$。

P2664 樹上游戲

路徑信息統計，考慮點分治。

由于顏色種類數是求并，很難直接做。

所以統計子樹信息，然后放到一起求并是不現實的，這里不能按照普通點分治的統計思路。是一種全新的處理方法。

對于當前分治中心的答案貢獻求解很簡單，就是 dfs 一遍即可，不再贅述。

考慮一條路徑 $x-rt-y$，對于 $y$ 的貢獻。如果 $c_u$ 在 $u-rt$ 中第一次出現，那么 $c_u$ 可以做出貢獻，具體來說 $u$ 子樹內的所有點都可以作為 $x$，對于 $rt$ 的其他子樹內的點（作為 $y$）做出貢獻 $sz_u$。這么做就是完成了 $x-rt$ 對于 $y$ 的貢獻，還需要完成 $rt-y$ 對于 $y$ 的貢獻，還是在第一次出現的時候統計，累加的大小就是對于當前分治中心其他所有子樹的大小（它們都可以作為 $x$），但是 $x-rt$ 的貢獻會和 $rt-y$ 的貢獻重復。于是在統計 $rt-y$ 路徑對 $y$ 的貢獻的時候，我們還需要時刻累加對應顏色外部 $\sum [x\to rt 的貢獻]$，減去即可。

有一個細節就是 $rt$ 對于其他點產生貢獻的影響，這個自己討論一下就行了。

P4183 [USACO18JAN] Cow at Large P

設點的深度和到葉子節點的距離分別是 $dep_i$ 和 $g_i$，一個點可以封鎖的條件就是 $dep_i \ge g_i$，可是我們要求封鎖點盡量少，也就希望這個點盡可能往上，等價于兒子滿足條件但父親不滿足這個條件。如果單純是條件一的話可以用換根 dp 來求，可是每個點的父親無法再換根，這就很難做。

觀察一下我們會發現這里其實是一個子樹產生 "1" 的貢獻，這里有一個公式就是子樹內 $\sum(2-deg_i)=1$，可以發現子樹內每個點都滿足 $dep_i\ge g_i$ 于是我們只需要對于每個滿足要求的點 $u$ 產生 $2-deg_u$ 的貢獻即可。點分治統計點對 $(u,v)$ 的貢獻。于是對于任意根節點 $r$，求 $\sum\limits_{d_{r,u\ge g_r(u)}}(2-deg_u)$。

點分治可以統計所有點對之間的貢獻，這也等價于每個點作為根的時候其他點的貢獻。于是本題可以用點分治求解。

用換根 dp 求出每個點到葉子的最短距離 $len_u$，然后以 $rt$ 為根的分治中每個點深度為 $d_u$。那么 $v$ 能對 $u$ 產生貢獻，必須滿足 $d_u\ge -d_v+len_v$。這個容易通過排序加雙指針解決。

注意一下，對于那個度數求和公式的使用，首先是無向樹，其次注意是“子樹”，所以子樹的根向上還有一個度也要算。

CF833D Red-Black Cobweb

對于邊占比的信息不太好直接合并出來，于是我們考慮維護 $a-kb$ 形式的信息使得合并之后可以快速查看是否滿足比例約束。

具體來說我們設黑邊個數為 $a$，白邊個數為 $b$，那么我們維護四個信息 $(A,B,C,D)=(a-2b,2b-a,b-2a，2a-b)$。

于是 $(u,v)$ 點對可以產生貢獻必須滿足，$A_u\le B_v$ 且 $C_u\le D_v$。這是一個二維數點的形式。

直接排序 $+$ 樹狀數組統計即可。如果去除同一子樹內貢獻呢，我們對于當前分治重心下同一子樹的信息單獨跑一邊上述計算減去貢獻即可。但是這么做感覺有點問題，就同一點對會產生重復貢獻，由于是乘法需要開根號，這就需要取模意義下的開根號也就是二次剩余有點麻煩。

為了防止點對產生重復貢獻，我們可以賦一個順序，也就是子樹順序，然后直接 CDQ 即可。

時間復雜度 $O(n\log^3 n)$。

邊分治

點分治產生多顆子樹，但是有的時候信息難以合并，這個時候就要用到邊分治這樣只會產生兩部分，方便操作。防止超時應該用多叉樹轉二叉樹

BZOJ 2870. 最長道路tree

求樹上的一條鏈使得 $len\times \min a_i 最大$。

直接對于邊 $i$ 進行邊分治即可，然后雙指針掃描。

\[ans=\max((f_x+f_y+1+val_i) \times \min(g_x,g_y)) \]

點分治做法就是維護每個最小值的最長鏈長。

動態點分治

就是多次詢問的要用到點分治結構的東西。

我們對于點分治的每層重心之間連邊得到的樹就是點分樹。不用顯示建樹，只需要記錄點分樹上的 $fa_u$ 即可，畢竟一般只需要用到暴力跳父親節點統計答案。

這樣子樹高是 $O(\log n)$ 級別的，我們可以暴力跳點分樹上的父親來求解答案，注意細節需要去掉父子之間重復的信息。

P6329 【模板】點分樹 | 震波

直接對于每個點 $u$ 維護自點分樹子樹內距離自己為 $k$ 的點權和，記為 $C_{0,u,k}$。

查詢就是不斷跳父親累加答案。思考一下為什么是這樣子，因為這本質是一個路徑統計問題，我們需要統計 $u-x$ 距離 $\le k$ 的 $\sum a_x$，路徑統計可以類似點分治的方法解決，但是多次詢問復雜度過高。在我們保存了各層分治中心之后，可以發現所有 $u-x$ 路徑必定可以拆分為 $u-anc-x$，其中 $anc$ 為 $u$ 在點分樹上的祖先，根據點分治統計的完全性，可以知道這個方法是正確的，可以這么拆。

下面還要解決兩個問題，一個是動態修改，很好辦，直接把 $C$ 替換為樹狀數組即可。還有一個就是 $u,fa_u$ 之間的統計重復。我們可以設 $C_{1,u,k}$ 表示在 $u$ 子樹內和 $fa_u$ 距離為 $k$ 的 $\sum a_x$。這樣子在兒子減去的，會在父親加回來。每次更新點權的時候就直接暴力跳父親，更新一路上的 $C_0$ 和 $C_1$。每次查詢的時候就直接一邊加 $C_0$ 的貢獻，一邊減去 $C_1$ 的貢獻。

其實從另一種視角看待 $u$ 和 $fa_u$ 之間的去重，其實就是我們在正常點分治過程中 $rt$ 的同一子樹內需要去重。以 $u$ 為分治中心的所有點，在 $fa_u$ 的視角中就是同一個子樹內的點，其貢獻需要減去，這么看是不是又有另一種理解了。

我們使用 vector 來儲存 $C$，對于 $C_{0,u}$ 直接開 $C$ 的最大深度大小，對于 $C_{1,u}$ 要開 $fa_u$ 的最大深度大小。

空間復雜度 $O(n\log n)$，時間復雜度 $O(n\log^2 n)$。

P3676 小清新數據結構題

樹鏈剖分解法

我們可以先動態維護根為 $1$ 的時候的答案。有一個很簡單的技巧就是把修改變為增加，對于一個點的修改影響的是所有祖先的子樹和，于是我們只需要支持快速鏈加，全局求和即可。$\sum (s_i+x)^2=s_i^2+2\times s_i\times x+x^2=\sum s_i^2+2x\sum s_i+len\times x^2$。樹鏈剖分維護即可。

然后考慮換根到 $u$，不妨設路徑為 $1=u_0-u_1-...-u_k=u$。跟為 $1$ 和 $u$ 的時候子樹和分為 $a_i$ 和 $b_i$。
答案為 $ans_u=ans_1-\sum\limits_{i=0}^ka_i^2+\sum\limits_{i=0}^kb_i^2$。

又因為 $a_{i+1}+b_i=a_0=b_k$（這一步是 key point），可以得到

\[\sum\limits_{i=0}^kb_i^2=\sum\limits_{i=1}^k(a_0-a_i)^2+a_0^2 \]

拆開維護一波即可。

點分樹做法

考慮將根從 $1$ 一步一步移動到 $u$，發現每次移動后都只有兩個值會發生變化，也就是 $s_{rt}\to sum-s_i$ 還有 $s_i \to s_{rt}$。

于是我們可以發現 $\sum(sum-s_i)\times s_i$ 為定值。

又因為 $\sum s_i^2$ 正是我們需要求解的值，所以我們只需要維護 $sum \times \sum s_i$ 即可。

$sum$ 很容易維護，現在的問題就在 $\sum s_i=\sum a_i\times (dis_{i,x}+1)$ 上面，這是動態點分治的模板。

在修改點權的情況下，$\sum(sum-s_i)s_i$ 是會變化的，我們需要快速求值。考慮一下這個式子的意義，其實就是沿著 $fa_i \to i$ 這條邊把整個樹劃分成兩個部分，然后兩個部分的點對乘積和。再對于所有劃分求和。

\[\begin{aligned} \sum(sum-s_i)s_i &= \sum\limits_{i=1}^n\sum\limits_{j=i+1}^na_i\times a_j\times dis(i,j) \\&=\sum\limits_{i=1}^n a_i \sum\limits_{j=i+1}^n a_j\times dis(i,j) \end{aligned} \]

單點修改，變化量就是 $(y-a_x)\times\sum\limits_{i=1}^na_j\times dis(x,j)$，又因為以 $x$ 為根的樹中，$\sum s_i=\sum\limits_{i=1}^na_i\times (dis(i,x)+1)$。所以直接維護即可。

P3345 [ZJOI2015] 幻想鄉戰略游戲

首先帶權重心的結論，每次往 $2\times sum_u\ge W$ 的子樹走即可。

線段樹解法

依據上述結論，直接線段樹二分。以 dfs 序為下標，子樹權值和 $sum_u$ 為值，記錄區間最大值。如果能往右邊走就走向右邊。

找到重心 $x$ 之后，考慮如何求出答案。

\[\begin{aligned}ans&=\sum\limits_{u}dis(x,u)\times a_u \\&=\sum\limits_{u}(dep_x+dep_u-2\times dep_{\mathrm {lca}}) a_u \end{aligned} \]

前兩個非常好維護，只需要維護 $\sum a_i$ 和 $\sum a_i\times dep_i$ 即可。對于第三個做法很神奇，就是把 $dep_{\mathrm {lca}}$ 再拆分細化成每個邊權的貢貢獻，對于每個點 $i$，將 $i-rt$ 路徑上的每條邊都加上 $a_i\times edge_j$，然后查詢 $x-rt$ 路徑和即可。用樹剖維護。

時間復雜度 $O(n\log^2 n)$。

點分樹解法

本題限制了 $deg_i\le 20$，其實不限制的話也可以三度化之后再做，詳見 LOJ6896. 幻想鄉戰略游戲加強版。

考慮如何找到重心，我們在點分樹上從根出發，遍歷所有兒子，看看誰的 $2\times sum_v\ge W$，走向它即可。度數限制保證了遍歷兒子復雜度的正確性，樹高為 $\log $ 級別的保證了遍歷點分樹復雜度的正確性。

但是還有一個問題，如圖黑邊為正常樹邊，藍邊為點分樹上的邊。在正常樹上行走是紅點走向橙點，然后橙點再向下找一個兒子繼續走。但是在點分樹上行走，我們是直接從紅點到了另外一個紅點。對于新的紅點，在原樹上存在向上行走的決策，也就是可能重心在橙色點以及其圖中左右部分中，所以我們是有可能從新紅點到橙色點的（橙色點為紅色點在點分樹上的子孫），但是我們這個時候的 $sum$ 信息就不對了，因為點分樹上所有點記錄的 $sum$ 只是其點分樹子樹內的權值和，并不包括外面這些 $W-sum_u$（也就是舊紅點以及其右邊部分，對應的也是以新紅點 $u$ 為根，橙色部分的子樹）。我們稱橙色點為接入點，每次需要在點分樹上對于接入點以及其點分樹上的祖先節點進行一個 $+W-sum_u$ 的操作，這樣才能保證 $sum$ 信息時刻正確。然后在每次尋找完重心之后，要撤銷這些增加操作。

找到重心之后還需要求解答案，這個就很好維護了吧。記錄一下自己點分樹子樹內的點權乘以邊權之和，還有到父親的點權乘以邊權之和減去即可。

時間復雜度 $O(nD\log n+n\log^2 n)$。

P11343 [KTSC 2023 R1] 出租車旅行

給定一顆 $n$ 個節點的樹，從 $u$ 一步走到 $v$ 的權值為 $a_u\times dis(u,v)+b_u$。求從 $1$ 走到其他所有點所需的最小權值和。$n\le 10^5$。

注意本篇題解包括上述描述中的 $a,b$ 數組和題面中的相反，讀者自行 $\rm {swap}$ 一下即可。

感受一下這個過程，本來可以一步到位的，我們之所以選擇一些途徑點，可能是因為當前點的 $a_u$ 太大了，我們需要走到一些 $a_u$ 比較小的點上再出發（和 $b_u$ 無關，因為從一個點出發，不管往哪里走都需要支付 $b_u$）。于是可以得到一個結論，我們途徑點的順序必然是從 $a_u$ 大的走到 $a_u$ 小的點，當然最后的終點不一定滿足這個條件。

于是考慮按照 $a_u$ 從大到小加入每個點作為途徑點的信息，對于每個點要從 $a_u$ 大于它的點中求出到它的最小距離，也要把它加入后續點的選擇中。直接做不好求，可以用點分治思想，如果經過 $rt$，從 $u$ 到 $v$ 的代價就是 $a_u\times d_v+(a_ud_u+b_u)$，這是一個一次函數可以用李超線段樹維護。這啟發我們建立點分樹，每個點維護其子樹內的一次函數，每次暴力跳父親求其最短路，然后暴力跳父親插入該點信息。

注意每次求完 $dis(1,u)$ 之后，需要 $b_u\gets dis(1,u)$，因為最短路需要類加上之前的路徑之和。

上面插入的是途徑點的信息，最后需要每個點作為終點再查詢一下就行了。