相似的兄弟 本节内容计 100 分，至少得 100 分可通过 反馈 我要提问 1000ms 131072K 有一无向连通图 GG（nn 个顶点，n - 1n−1 条边，点从 11 到 nn 依次编号）。当然，你能看出这其实就是一棵树，请找出所有满足以下条件的节点： 该节点不是叶子节点（度不为 00）。 该节点下面所有的子树大小必须相同（如果下面只有一棵子树也默认为相同）。 注意，该树为有根树，你需要先找到它的根才能开始访问其他节点。 请你设计程序，完成上面要求。 输入格式 第一行包含 11 个整数 nn。 接下来 n-1n−1 行，每行包含 22 个用空格隔开的正整数 uu、vv，表示编号为 uu 和编号为 vv 的点之间有边相连，其中 uu 是 vv 的父亲节点。

这道题目的意思是，给定一棵树，要求找出所有满足以下两个条件的节点：

1. 该节点不是叶子节点（度不为0）。
2. 该节点下面所有的子树大小必须相同（如果下面只有一棵子树也默认为相同）。

为了解决这个问题，我们可以使用一种称为递归的算法。我们从根节点开始，递归遍历整棵树，对于每一个节点，我们先判断它是否为叶子节点，如果是，则跳过；如果不是，则遍历它的每一个子节点，统计它们的子树大小，并判断是否相等。如果相等，则将该节点加入结果集；如果不相等，则跳过该节点。

下面是一个简单的递归算法的代码实现：

void findNodes(Node* root, vector<int>& res) {
    // 如果当前节点是叶子节点，则跳过
    if (root->children.empty()) return;

    bool equal = true;
    int size = root->children[0]->size;
    // 遍历当前节点的每一个子节点
    for (int i = 1; i < root->children.size(); i++) {
        // 如果有子树大小不相等，则退出循环
        if (root->children[i]->size != size) {
            equal = false;
            break;
        }
    }

    // 如果所有子树大小相

相关问题

帮我做题相似的兄弟 本节内容计 100 分，至少得 100 分可通过 反馈 我要提问 1000ms 131072K 有一无向连通图 GG（nn 个顶点，n - 1n−1 条边，点从 11 到 nn 依次编号）。当然，你能看出这其实就是一棵树，请找出所有满足以下条件的节点： 该节点不是叶子节点（度不为 00）。 该节点下面所有的子树大小必须相同（如果下面只有一棵子树也默认为相同）。 注意，该树为有根树，你需要先找到它的根才能开始访问其他节点。 请你设计程序，完成上面要求。 输入格式 第一行包含 11 个整数 nn。 接下来 n-1n−1 行，每行包含 22 个用空格隔开的正整数 uu、vv，表示编号为 uu 和编号为 vv 的点之间有边相连，其中 uu 是 vv 的父亲节点。 输出格式 输出共 11 行，包含若干个整数，之间用空格隔开，表示为满足题目要求的节点编号。 注意，输出的顺序要按照编号 从小到大 进行输出。 数据范围

首先，这是一道树形 DP 的题目。

对于每一个节点 $u$，我们可以用一个数组 $size_u$ 来表示这个节点的子树大小。我们可以使用一个递归函数来计算 $size_u$，每次向下递归时将 $size_u$ 的值加上 $size_v$，其中 $v$ 是 $u$ 的子节点。

然后，我们可以使用另一个递归函数来找出所有满足条件的节点。对于每个节点 $u$，我们可以使用一个数组 $ok_u$ 来表示这个节点的子树是否满足题目的条件。当 $ok_u=1$ 时，表示 $u$ 的子树满足题目的条件；当 $ok_u=0$ 时，表示 $u$ 的子树不满足题目的条件。

我们可以使用下面的算法来求解这道题：

1. 使用递归函数计算每个节点的子树大小 $size_u$。

2. 使用递归函数递归遍历每个节点 $u$，如果 $u$ 不是叶子节点，则检查它的所有子节点 $v$，看看是否满足以下条件：

- $ok_v=1$，表示 $v$ 的子树满足题目的条件。
- $size_v=size_u/2$，表示 $u$ 的子树的大小为 $u$ 的子节点的子树的大小的两倍。

如

一个无向非连通图共有20条边，则至少有（ ）个顶点。 A 7 B 8 C 9 D 10

由于一个无向非连通图可以被划分为若干个连通子图，而每个连通子图中的每个顶点都至少有一条边与其相连，因此该图至少包含连通子图的个数个顶点。又因为连通子图中的边数不少于顶点数减1，所以连通子图的边数之和不少于顶点数减去连通子图的个数。设该图包含k个连通子图，那么有20≥n-k，即k≥n-20。又因为每个连通子图至少包含一个顶点，所以n≥k，即n≥n-20，因此n至少为20+1=21。所以答案为D 10。