最新要闻

广告

手机

音乐剧《没有共产党就没有新中国》将全北京展演

音乐剧《没有共产党就没有新中国》将全北京展演

 瞳景物联财务负责人李灏辞职 2022年公司净利1598.92万 环球速递

瞳景物联财务负责人李灏辞职 2022年公司净利1598.92万 环球速递

家电

  1. 首页
  2. 资讯
  3. 内容

【CF1842F】Tenzing and Tree_今日热门

来源：博客园


(相关资料图)

题目

题目链接：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 |\]

这个绝对值很讨厌，但可以发现，如果点 \(rt\) 是所有黑点的重心的话，那么对于所有的 \(cnt[i]\ (i\neq rt)\)，都一定满足 \(2\times cnt[i]\leq k\)，此时答案就是

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

我们发现如果选择点 \(x\) 染黑，那么从 \(x\) 的父亲到 \(rt\) 上所有点的 \(cnt\) 都要加一。那么为了最大化答案，我们只需要选择深度最小的 \(k\) 个节点染黑即可。只需要枚举每一个点作为 \(rt\)，然后 BFS 计算所有 \(k\) 的答案即可。即使目前枚举的点不是重心也没关系，因为这样就会导致有些 \(k-2\times cnt<0\)，不会比最优答案大。时间复杂度 \(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

关键词：