网站运营培训学校,湖南省网站备案登记,jf厂高仿手表网站,桂林网站建设内容树的重心
给定一颗树#xff0c;树中包含 n n n 个结点#xff08;编号 1 ∼ n 1∼n 1∼n#xff09;和 n − 1 n−1 n−1条无向边。请你找到树的重心#xff0c;并输出将重心删除后#xff0c;剩余各个连通块中点数的最大值。 重心定义#xff1a; 重心是指树中的一…树的重心
给定一颗树树中包含 n n n 个结点编号 1 ∼ n 1∼n 1∼n和 n − 1 n−1 n−1条无向边。请你找到树的重心并输出将重心删除后剩余各个连通块中点数的最大值。 重心定义 重心是指树中的一个结点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点被称为树的重心。
输入格式
第一行包含整数 n n n表示树的结点数。
接下来 n − 1 n−1 n−1 行每行包含两个整数 a a a 和 b b b表示点 a a a 和点 b b b 之间存在一条边。
输出格式
输出一个整数 m m m表示将重心删除后剩余各个连通块中点数的最大值。
数据范围 1 ≤ n ≤ 105 1≤n≤105 1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6输出样例
4思路
基本框架 D F S DFS DFS判断一个结点是否是重心的方法 假设当前按照深度优先的次序遍历到第 k k k 个结点我们删除这个结点之后会得到第 k k k 个结点的若干子树每个子树都是一个连通块以及一个包含第 k k k 个结点的父节点的连通块。 对于第 k k k 个结点的若干子树我们可以通过递归的方式将子树的返回值设置为子树的节点数量这样就可以非常高效地获取每个子树所对应的连通块的节点数量 而对于包含第 k k k 个结点的父节点的连通块它的节点数量可以由如下公式计算 F n − s u m − 1 Fn-sum-1 Fn−sum−1其中 n n n 为树的总节点数 s u m sum sum为所有子树构成的连通块的结点总数1代表第 k k k 个结点 而我们的目标是求出将重心删除后剩余各个连通块中点数的最大值因此可以设置一个全局变量保存答案然后在 D F S DFS DFS 的过程中不断更新它具体更新的方式见代码。
代码
#include iostream
#include vector
#include algorithm
using namespace std;
//树的重心链式前向星DFS
const int maxn 1e5 1;
int n, head[maxn], len 0, vis[maxn], ans 1e6 - 5;struct Node {int to, next;
}e[2 * maxn];void add_edge(int u, int v) {e[len].to v;e[len].next head[u];head[u] len;
}int dfs(int k) {int son_max 0, sum 0;for (int i head[k]; i; i e[i].next) {int v e[i].to;if (!vis[v]) {vis[v] 1;int v_num dfs(v);vis[v] 0;sum v_num;son_max v_num son_max ? v_num : son_max;}}// 更新答案ans min(ans, max(son_max, n - sum - 1));return sum 1;
}int main() {cin n;for (int i 1; i n; i) {int u, v; cin u v;add_edge(u, v);add_edge(v, u);}dfs(1);cout ans;return 0;
}
