Codeforces 1187E - Tree Painting(树上所有节点的儿子数量和最大)
2024-09-07 18:37:48
乍一看题意比较麻烦,好像要删点求联通性,但其实是相当于求以某一个节点为根时,他的所有后代(儿子,儿子的儿子等等)的儿子的总和最大。
两边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 ;
}
最新文章
- java中的等于
- 数学 SRM 690 Div1 WolfCardGame 300
- 在GoF设计模式
- boolean 和 Boolean 类型数据的差别
- install 命令用法详解
- Balance
- Solr部署如何启动
- 台湾书籍代购网址&mdash;&mdash;2013-08-25 16
- ZEngine游戏框架需求稿
- ACM题目推荐(刘汝佳书上出现的一些题目)[非原创]
- Spring之SpringMVC的MethodNameResolver(源码)分析
- js 指定位置插入html标签(可编辑div)
- 写了一下午的dijkstra。突然发现我写的根本不是dijkstra。。。。是没优化过的BFS.......
- Moya 浅析
- Linux学习 -- 备份与恢复
- Hexo next博客添加折叠块功能添加折叠代码块
- Linux 修改SWAP分区后导致开机问题
- <;? extends T>;和<;? super T>;的理解
- 剥开比原看代码03:比原是如何监听p2p端口的
- Linux:【解决】无法连接 MKS:套接字连接尝试次数太多正在放弃