乍一看题意比较麻烦,好像要删点求联通性,但其实是相当于求以某一个节点为根时,他的所有后代(儿子,儿子的儿子等等)的儿子的总和最大。

两边dfs即可,第一遍dfs随便找一个点为根,求出每个节点的儿子数siz[],第二遍dfs以每个点作为根更新ans。

这里注意:如果u为根,u是v的父亲,且此时u后代的和为siz[u] = val,那么v为根时后代和为val-siz[v]+n-siz[v],以此关系作为第二遍dfs的依据、

#include <bits/stdc++.h>
using namespace std; const int maxn = 2e5 + ;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int n, tot, head[maxn], siz[maxn];
struct edge{
int to, next;
} ed[maxn<<];
ll ans;
inline void init(){
memset( head, -, sizeof(head) );
tot = ; ans = ;
for( int i=; i<=n; i++ ) siz[i] = ;
} inline void add( int u, int v ){
ed[++tot].to = v; ed[tot].next = head[u]; head[u] = tot;
ed[++tot].to = u; ed[tot].next = head[v]; head[v] = tot;
} inline void FindSiz( int x, int fa ){
for( int i=head[x]; i!=-; i=ed[i].next ){
int y =ed[i].to;
if( y!=fa){
FindSiz(y, x);
siz[x] += siz[y];
}
}
ans += siz[x];
} inline void dfs( int x, int fa, ll val ){
for( int i=head[x]; i!=-; i=ed[i].next ){
int y = ed[i].to;
if( y==fa ) continue;
ll tmp = val-siz[y]+n-siz[y];
ans = max( ans ,tmp );
dfs( y, x, tmp );
}
} int main(){
scanf("%d", &n);
init();
for( int i=; i<n; i++ ){
int u, v;
scanf("%d%d", &u, &v);
add( u, v );
}
FindSiz(, );
dfs( , , ans );
printf("%lld\n", ans); return ;
}

最新文章

  1. java中的等于
  2. 数学 SRM 690 Div1 WolfCardGame 300
  3. 在GoF设计模式
  4. boolean 和 Boolean 类型数据的差别
  5. install 命令用法详解
  6. Balance
  7. Solr部署如何启动
  8. 台湾书籍代购网址&mdash;&mdash;2013-08-25 16
  9. ZEngine游戏框架需求稿
  10. ACM题目推荐(刘汝佳书上出现的一些题目)[非原创]
  11. Spring之SpringMVC的MethodNameResolver(源码)分析
  12. js 指定位置插入html标签(可编辑div)
  13. 写了一下午的dijkstra。突然发现我写的根本不是dijkstra。。。。是没优化过的BFS.......
  14. Moya 浅析
  15. Linux学习 -- 备份与恢复
  16. Hexo next博客添加折叠块功能添加折叠代码块
  17. Linux 修改SWAP分区后导致开机问题
  18. &lt;? extends T&gt;和&lt;? super T&gt;的理解
  19. 剥开比原看代码03:比原是如何监听p2p端口的
  20. Linux:【解决】无法连接 MKS:套接字连接尝试次数太多正在放弃

热门文章

  1. 【技术博客】nginx服务器的https协议实现
  2. c# 创建socket连接辅助类-可指定超时时间
  3. (转)解决mybatis的mapper.xml查询不出数据,结果一直为null问题
  4. SpringBoot系列教程web篇Listener四种注册姿势
  5. 浅析PHP框架Laravel最新SQL注入漏洞
  6. 【剑指offer】孩子们的游戏(圆圈中最后剩下的数)
  7. 【简记】修改Docker数据目录位置,包含镜像位置
  8. Java学习:Lambda表达式
  9. 基准测试工具:Wrk初识
  10. 使用SqlConnectionStringBuilder构造数据库连接字符串