相似的兄弟 本节内容计 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. 该节点下面所有的子树大小必须相同（如果下面只有一棵子树也默认为相同）。

输入格式中给定了有 n 个顶点和 n-1 条边的信息，表示这是一棵有根树。接下来 n-1 行给出了边的信息，表示编号为 u 和编号为 v 的点之间有边相连，其中 u 是 v 的父亲节点。

为了解决这道题，我们需要遍历整棵树，对于每个节点都计算其子树大小，然后检查是否满足条件 1 和条件 2。

我们可以使用递归的方法来遍历树，对于每个节点，我们先统计它的子树大小，然后检查是否满足条件 1 和条件 2。如果满足条件，就将该节点加入答案中。然后再对该节点的每个子节点递归调用函数，继续遍历整棵树。

下面是参考代码：

def dfs(node, parent):
    # 统计该节点的子树大小
    size = 1
    for child in children[node]:
        if child == parent:
            continue
        size += dfs(child, node)

相关问题

相似的兄弟 本节内容计 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$ 的子节点的子树的大小的两倍。

如