【CF1842F】Tenzing and Tree

來(lái)源： 博客園 2023-06-27 21:17:57


(資料圖)

題目

題目鏈接：https://codeforces.com/contest/1842/problem/F給定一棵 \(n\) 個(gè)點(diǎn)的樹(shù)，你可以選擇其中 \(k\) 個(gè)點(diǎn)染黑，定義一條邊的價(jià)值為割去這條邊之后，剩下兩顆樹(shù)的黑點(diǎn)數(shù)量差；一棵樹(shù)的價(jià)值為所有邊的價(jià)值之和。對(duì)于 \(k\in [0,n]\)，求出樹(shù)的價(jià)值的最大值。\(n\leq 5000\)。

思路

不妨設(shè)點(diǎn) \(rt\) 為根，設(shè) \(cnt[i]\) 表示以 \(i\) 為根的子樹(shù)內(nèi)的黑點(diǎn)數(shù)量。那么如果染 \(k\) 個(gè)黑點(diǎn)，答案就是

\[\sum^{}_{i\neq rt}\left |(k-cnt[i])-cnt[i]\right |=\sum^{}_{i\neq rt}\left |k-2\times cnt[i]\right |\]

這個(gè)絕對(duì)值很討厭，但可以發(fā)現(xiàn)，如果點(diǎn) \(rt\) 是所有黑點(diǎn)的重心的話(huà)，那么對(duì)于所有的 \(cnt[i]\ (i\neq rt)\)，都一定滿(mǎn)足 \(2\times cnt[i]\leq k\)，此時(shí)答案就是

\[(n-1)\times k - 2\times \sum_{i\neq rt}cnt[i]\]

我們發(fā)現(xiàn)如果選擇點(diǎn) \(x\) 染黑，那么從 \(x\) 的父親到 \(rt\) 上所有點(diǎn)的 \(cnt\) 都要加一。那么為了最大化答案，我們只需要選擇深度最小的 \(k\) 個(gè)節(jié)點(diǎn)染黑即可。只需要枚舉每一個(gè)點(diǎn)作為 \(rt\)，然后 BFS 計(jì)算所有 \(k\) 的答案即可。即使目前枚舉的點(diǎn)不是重心也沒(méi)關(guān)系，因?yàn)檫@樣就會(huì)導(dǎo)致有些 \(k-2\times cnt<0\)，不會(huì)比最優(yōu)答案大。時(shí)間復(fù)雜度 \(O(n^2)\)。

代碼

#include using namespace std;const int N=5010;int n,dep[N],ans[N];vector e[N];queue q;int main(){scanf("%d",&n);for (int i=1,x,y;i

關(guān)鍵詞：

你可能會(huì)喜歡：