題目大意:? 有棵樹以1為根結(jié)點(diǎn)，每條邊長度都是k, 定義樹的cost為離樹根最遠(yuǎn)的點(diǎn)到樹根的距離, 一次操作可以花費(fèi)c將樹根移到樹根任意一個(gè)相鄰點(diǎn), 利潤為樹此時(shí)的cost減去形成該樹的操作花費(fèi), 輸出最大利潤。

不難想到一個(gè)暴力枚舉的算法, 也就是枚舉每一個(gè)根節(jié)點(diǎn) n, 然后計(jì)算最遠(yuǎn)距離更新答案, 時(shí)間復(fù)雜度為 O()， 超時(shí)。。。

那么怎么把時(shí)間復(fù)雜度降下來呢？?我們可以把樹看作成一個(gè)無向圖, 然后可以使用換根dp, 先定義我們的狀態(tài)表示的集合

dp[u][0]: 以 u 為根節(jié)點(diǎn)時(shí)向下走的最大距離

dp[u][1]: 以 u 為根節(jié)點(diǎn)時(shí)向下走的第二大距離

我們利用 換根 dp 的思想先計(jì)算出題目中任意?u?為 根節(jié)點(diǎn)先下中的情況, 也就是 dp[u][0], dp[u][1], 這可以使用 dfs 來實(shí)現(xiàn)。

換根 dp 的思想就是更新每次換根節(jié)點(diǎn)時(shí)對答案的貢獻(xiàn)。

接下來我們來推導(dǎo)狀態(tài)轉(zhuǎn)移方程, 假設(shè)我們從 父節(jié)點(diǎn) fa 換根到子節(jié)點(diǎn) u, 此時(shí)想得到最大距離無非就兩條路徑: 向上走或者向下走

我們先考慮向下走的情況, 很明顯為 dp[u][0]

我們考慮向上走的情況, 假設(shè)最大距離為 len, 為了避免路徑重新經(jīng)過 u, 會有兩種情況:

當(dāng)從 父節(jié)點(diǎn) fa 向下走得到最大距離路徑中不包含 u 時(shí):

len = max(dp[fa][0], len_fa) + 1

當(dāng)從 父節(jié)點(diǎn) fa 向下走得到最大距離路徑中包含 u 時(shí), 由于路徑重新經(jīng)過 u 會時(shí)答案變得沒有意義，我們需要換條次大的路徑:

len = max(dp[fa][1], len_fa) + 1

我們在遞歸時(shí)可以使用變量 cnt 定義為換根的次數(shù)。

于是更新答案: ans = max(ans, max(dp[u][0], len) * k - c * cnt)

時(shí)間復(fù)雜度O(n) 代碼:

解法參考自:?https://zhuanlan.zhihu.com/p/624893947