给出一个有n个节点，n 減 1条边的连通图，每条边长均为1。除此之外，现在原图上的每两个不相邻且仅间隔一个节点的节点间建边，边长仍为1。 求对于所有的点对左小括號 u 逗號 v 右小括號，加總 從 空白 到 空白 對 d i s t 左小括號 u 逗號 v 右小括號。其中d i s t 左小括號 u 逗號 v 右小括號指的是左小括號 u 逗號 v 右小括號之间的最短距离。

题目描述：

给出一个有n个节点的连通图，每条边的长度均为1。除此之外，现在在原图上的每两个不相邻且仅间隔一个节点的节点间建立了一个节点。所有新加入的节点两两之间的距离均为1。

对于所有给定的点对左小括号u，v右小括号，加总从空白到空白对dist左小括号u,v右小括号左小括号沿原图边行进的距离加上建立的节点之间路径的长度，左小括号dist左小括号u,v右小括号右小括号表示第u个节点与第v个节点之间的距离。

其中dist左小括号u,v右小括号表示点u到点v的最短路径中边的条数，即点u到点v之间的最短距离。

解题思路：

本题目的是求距离一个节点两个单位距离的两个节点之间的最短路径边数。可以使用广度优先搜索(BFS)求解。

对于每次搜索，先加入点u，将该点u周围一度节点加入队列；对于队列中添加过的元素，说明距离起点的距离为1；对于从队列中取出的元素v，将该节点周围未添加过的一度节点加入队列；以此类推，直至遍历完所有节点。

使用邻接表储存图的信息。

在BFS的过程中，遍历到以上情况时，可将当前节点及其相邻节点删去，并记录当前的dist。

Python 代码：

相关问题

为什么满二叉树叶子节点个数是n，度为2的节点个数就是n减1

满二叉树是指除了最后一层，其余每层节点数都是满的且最后一层的节点都靠左排列的二叉树。由于每个节点最多只有两个左右子节点，所以满二叉树的叶子节点只能出现在最后一层，且只有最后一层的节点数等于叶子节点的个数。而满二叉树度为2的节点都有左右两个子节点，除了最后一层没有度为2的节点外，其余每层都有度为2的节点出现，而每一层的度为2的节点个数都比叶子节点个数少1个，所以满二叉树叶子节点个数是n，度为2的节点个数就是n减1。

c++给出一数字 n，计算包含n个节点的二叉树数目有多少个。

对于包含 n 个节点的二叉树，我们可以将其划分成由一个根节点、左子树和右子树组成的三个部分。假设左子树有 i 个节点，右子树有 n-1-i 个节点，则可以通过左子树和右子树的组合方式得到包含 n 个节点的二叉树。

因此，我们可以通过枚举左子树节点数来计算包含 n 个节点的二叉树数目。设 f(n) 表示包含 n 个节点的二叉树数目，则可以得到递推公式：

f(n) = ∑(f(i) * f(n-1-i)), i = 0 ~ n-1

初始状态为 f(0) = 1，因为空树也算一棵二叉树。

下面是C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << numTrees(n) << endl;
    return 0;
}

时间复杂度为 O(n^2)，空间复杂度为 O(n)。