[JLOI2009] 二叉树问题
题目描述
如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：
- 深度：
$4$ - 宽度：
$4$ - 结点 8 和 6 之间的距离：
$8$ - 结点 7 和 6 之间的距离：
$3$
其中宽度表示二叉树上同一层最多的结点个数，节点 $u, v$ 之间的距离表示从 $u$ 到 $v$ 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。
给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 $x, y$ 之间的距离。
输入格式
第一行是一个整数，表示树的结点个数 $n$。
接下来 $n - 1$ 行，每行两个整数 $u, v$，表示树上存在一条连接 $u, v$ 的边。
最后一行有两个整数 $x, y$，表示求 $x, y$ 之间的距离。
输出格式
输出三行，每行一个整数，依次表示二叉树的深度、宽度和 $x, y$ 之间的距离。
样例 #1
样例输入 #1
10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
6 10
8 6
样例输出 #1
4
4
8
提示
对于全部的测试点，保证 $1 \leq u, v, x, y \leq n \leq 100$，且给出的是一棵树。
解题思路
求树的深度，就是求节点到根节点的距离最大值。
求树的宽度，就是求同一深度节点（到根节点距离相同）的数量最大值。
Floyd算法
计算任意两点的最短路径
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = MIN(graph[i][j], graph[i][k]+graph[k][j]);
}
}
}
计算通过k处，i节点到j节点的最短距离
AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAX(a, b) ((a)<(b)?(b):(a))
#define MIN(a, b) ((a)<(b)?(a):(b))
int n;
int graph[100][100];
int main() {
cin >> n;
int u, v;
memset(graph, 0, sizeof(graph));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j) graph[i][j] = INT_MAX/2;
}
}
for (int i = 0; i < n-1; i++) {
cin >> u >> v;
graph[u][v] = 1;
graph[v][u] = 2;
}
cin >> u >> v;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = MIN(graph[i][j], graph[i][k]+graph[k][j]);
}
}
}
int depth = 0, width = 0, max = 0;
int d[100] = {0};
for (int i = 2; i <= n; i++) {
depth = MAX(graph[1][i], depth); // 枚举到根节点的深度
d[graph[1][i]]++; // 不同深度计数
}
for (int i = 1; i <= depth; i++) {
width = MAX(d[i], width); // 遍历不同深度的节点数量，计算最大值
}
cout << depth+1 << endl; // 根节点深度为1
cout << width << endl;
cout << graph[u][v] << endl;
}