首页 > 极客资料 博客日记
CF1187E 题解
2024-10-20 15:00:04极客资料围观17次
极客之家推荐CF1187E 题解这篇文章给大家,欢迎收藏极客之家享受知识的乐趣
Title translation
给定一棵 \(n\) 个点的树,初始全是白点。
要做 \(n\) 步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点,求可获得的最大权值。
Solution
如何让这道题秒降绿题呢?
先简化一下题意:
给定一个 \(n\) 个点的树,请求出一个结点,使得以这个结点为根时,所有结点的深度之和最大,求这个深度。
这不和P3478一样吗!
为何是这样?
我们换个方向思考:
因为每一次是把一个与一个黑点相隔一条边的白点染成黑点,考虑一个节点 \(v\),当这棵树的根节点是 \(v\)、\(v\) 的父亲、\(v\) 的父亲的父亲……的时候,\(v\) 都会给它们所在的联通块大小贡献 \(1\)。那它最多贡献多少个 \(1\) 呢?其实就是它自己的深度。
那题目就简化成了刚刚的那样……
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Maxn=1e6+5;
int n;vector<int>e[Maxn];
int Size[Maxn],Dep[Maxn];
int f[Maxn];
void dfs1(int u,int fa){
Size[u]=1;Dep[u]=Dep[fa]+1;
for(auto v:e[u]){
if(v==fa)continue;
dfs1(v,u);
Size[u]+=Size[v];
}
}
void dfs2(int u,int fa){
for(auto v:e[u]){
if(v==fa)continue;
f[v]=f[u]+n-2*Size[v];
dfs2(v,u);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
for(int i=1;i<=n;i++)f[1]+=Dep[i];
dfs2(1,0);int maxn=INT_MIN,id;
for(int i=1;i<=n;i++)
if(f[i]>maxn)maxn=f[i],id=i;
cout<<maxn;
return 0;
}
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”