题目链接

题意:给你一棵无根树,每次你可以选择一个点从白点变成黑点(除第一个点外别的点都要和黑点相邻),变成黑点后可以获得一个权值(白点组成连通块的大小) 问怎么使权值最大

思路:首先,一但根确定了,整棵树的权值就只需要模拟即可,所以思路就转换为求哪一个点为根的权值最大。

这题需要用到一个二次扫描换根的思想,我们可以先从任意一个点去进行树形dp 并且得到从这个点开始去逐渐更新他的儿子节点

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define ll long long int
using namespace std;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int moth[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int dir[4][2]={1,0 ,0,1 ,-1,0 ,0,-1};
int dirs[8][2]={1,0 ,0,1 ,-1,0 ,0,-1, -1,-1 ,-1,1 ,1,-1 ,1,1};
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;
int n;
vector<int> G[200007];
ll dp[200007]; //表示i节点以下的所有贡献
ll f[200007]; //以i为根的权值
ll nump[200007]; //儿子节点数(包含自己)
void dfs(int u,int fa){
nump[u]=1;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
dfs(v,u);
nump[u]+=nump[v];
}
}
void dfss(int u,int fa){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
dfss(v,u);
dp[u]+=dp[v];
}
dp[u]+=nump[u];
}
void change(int u,int fa){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
f[v]=f[u]-nump[v]-dp[v]+n-nump[v]+dp[v]; //核心代码
change(v,u);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++){
int u,v; cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
dfss(1,0);
f[1]=dp[1];
change(1,0);
ll ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,f[i]);
}
cout<<ans<<"\n";
return 0;
}

最新文章

  1. Python traceback【转】
  2. 深入理解Bindler
  3. oracle 客户端单独配置
  4. 【云计算】docker相关开源项目、工具
  5. DataContract
  6. squid ACL 大全
  7. android文章学习 侧滑菜单实现
  8. 百度网盘,前几天刚从百度云改名过来,百度云这个名字给之前的百度开放云(同步盘用户比较小众)good
  9. 负载均衡-多台机子session不起效:把php.ini中file改为memcache存储
  10. 用自动化运维工具解放IT运维
  11. T-SQL 操作文件 具体解释
  12. 执行 apt-get -f install 提示错误
  13. C各个类型的大小
  14. Linux添加系统调用的两种方法
  15. java--加强之 Java5的线程并发库
  16. ios键盘弹起 body的高度拉长,页面底部空白问题。ios软键盘将页面抵到上面后,关闭软键盘页面不回弹的问题。
  17. attr跟prop的区别:
  18. 打造适合自己的vim编辑器方法总结
  19. Java框架spring 学习笔记(十八):事务管理(xml配置文件管理)
  20. Redhat上为java Maven项目构建基于Jenkins + Github的持续集成环境

热门文章

  1. NOIP初赛篇——07信息编码表示
  2. Debian9 升级至 Debian10
  3. Laya 踩坑日记-BitmapFont 不显示空格
  4. 【MyBatis】MyBatis 多表操作
  5. jenkins + Ansible Plugin + ansi-color 让结果显示颜色
  6. EntityFramework Core如何映射动态模型?
  7. uni-app开发经验分享四: 实现文字复制到选择器中
  8. Bitter.Core系列二:Bitter ORM NETCORE ORM 全网最粗暴简单易用高性能的 NETCore ORM 之数据库连接
  9. 在线配置热加载配置 go-kratos.dev 监听key
  10. 手淘架构组最新实践 | iOS基于静态库插桩的⼆进制重排启动优化 抖音研发实践:基于二进制文件重排的解决方案 APP启动速度提升超15% 编译期插桩