【CF1842F】Tenzing and Tree
來源：
博客園
2023-06-27 21:17:57
(資料圖)
題目
題目鏈接：https://codeforces.com/contest/1842/problem/F給定一棵 \(n\) 個點的樹，你可以選擇其中 \(k\) 個點染黑，定義一條邊的價值為割去這條邊之后，剩下兩顆樹的黑點數量差；一棵樹的價值為所有邊的價值之和。對于 \(k\in [0,n]\)，求出樹的價值的最大值。\(n\leq 5000\)。
思路
不妨設點 \(rt\) 為根，設 \(cnt[i]\) 表示以 \(i\) 為根的子樹內的黑點數量。那么如果染 \(k\) 個黑點，答案就是
\[\sum^{}_{i\neq rt}\left |(k-cnt[i])-cnt[i]\right |=\sum^{}_{i\neq rt}\left |k-2\times cnt[i]\right |\]這個絕對值很討厭，但可以發(fā)現(xiàn)，如果點 \(rt\) 是所有黑點的重心的話，那么對于所有的 \(cnt[i]\ (i\neq rt)\)，都一定滿足 \(2\times cnt[i]\leq k\)，此時答案就是
\[(n-1)\times k - 2\times \sum_{i\neq rt}cnt[i]\]我們發(fā)現(xiàn)如果選擇點 \(x\) 染黑，那么從 \(x\) 的父親到 \(rt\) 上所有點的 \(cnt\) 都要加一。那么為了最大化答案，我們只需要選擇深度最小的 \(k\) 個節(jié)點染黑即可。只需要枚舉每一個點作為 \(rt\)，然后 BFS 計算所有 \(k\) 的答案即可。即使目前枚舉的點不是重心也沒關系，因為這樣就會導致有些 \(k-2\times cnt<0\)，不會比最優(yōu)答案大。時間復雜度 \(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 關鍵詞：
