POJ 1655 Balancing Act (树的重心,常规)
2024-08-27 20:28:16
题意:求树的重心,若有多个重心,则输出编号较小者,及其子树中节点最多的数量。
思路:
树的重心:指的是一个点v,在删除点v后,其子树的节点数分别为:u1,u2....,设max(u)为其中的最大值,点v的max(u)是所有点里面最小的,称v为树的重心。
如何求任一重心?按树形来看,max(v)可以由其父亲贡献,也可以由其任一孩子贡献。孩子比较好解决,不就是深搜一遍,然后回溯时统计下数量就行了?而父亲的怎么办?可以知道,点v到其父亲这一叉就是n-sum(v)了,sum(v)指的是以v为根的子树的节点数。那么一次DFS就可以知道答案了,复杂度O(n)。
//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
int n, vis[N], cnt[N];
vector<int> vect[N];
int DFS(int x) //深搜求删除任一点后,其某一子树的节点数量达到的最大值。
{
vis[x]=;
int big=,sum=;
for(int i=; i<vect[x].size(); i++)
{
if(!vis[vect[x][i]])
{
int t=DFS(vect[x][i]);
big=max(t,big);
sum+=t;
}
}
cnt[x]=max(big, n-sum-);
return sum+;
} int main()
{
//freopen("input.txt", "r", stdin);
int t,a,b;cin>>t;
while(t--)
{
scanf("%d",&n);
memset(vis,,sizeof(vis));
memset(cnt,,sizeof(cnt));
for(int i=; i<=n; i++) vect[i].clear();
for(int i=; i<n; i++)
{
scanf("%d%d",&a,&b);
vect[a].push_back(b);
vect[b].push_back(a);
}
DFS();
int big=INF, pos;
for(int i=; i<=n; i++)
{
if(cnt[i]<big)
{
big=cnt[i];
pos=i;
}
}
printf("%d %d\n", pos, big);
}
return ;
}
AC代码
最新文章
- tomcat发布脚本
- 外网访问原理分析 - 每天5分钟玩转 OpenStack(105)
- spring初次体验
- unity3d android 优化
- [Java面试二]Java基础知识精华部分.
- 编程作业—C++初探 简单的学生信息处理程序实现
- MSP430常见问题之电源类
- jquery 在页面中按回车 响应 事件
- Codeforces Round #306 (Div. 2) ABCDE(构造)
- C#.net连接SQLite及遇到的问题
- 第四章 android 命名规范和编码规范
- 理解交互设计之";行为设计与对象设计";
- MongoDB数据库索引
- Angular 向组件传递模板的几种方法
- [总结] 二维ST表及其优化
- MacOs 安装cordova报无权访问题解决方案
- MyEclipse导入Maven项目以及Maven转化为Dynamic Web Module(转)
- JSON parse error: Cannot deserialize instance of `int` out of START_OBJECT token; nested exception is com.fasterxml.jackson.databind.exc
- 4J - 前m大的数
- python调用dll方法