最新要闻

广告

手机

问“题”于民｜换乘站入口标识，能否全面、了然？

问“题”于民｜换乘站入口标识，能否全面、了然？

 3000元化妆品用完后空瓶竟卖300元-天天热门

3000元化妆品用完后空瓶竟卖300元-天天热门

家电

  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

关键词：