在一棵n叉树中，找出每个节点的较大子节点的数量，时间复杂度为O(N)？

Question

我在尝试降低算法复杂性时遇到了算法问题。具体问题有以下输入：

• 第一行是一个整数N：n叉树的节点总数（1 <= N <= 10^5).
• 接下来的N行是每个节点的值，称为Vi，其中1 <= Vi <= 10^9.
• 接下来的N-1行是子节点和父节点的关系（从2到N），默认第一个节点为根节点。

结果： 打印N行，每行包含值大于其父节点的子节点（包括低级子节点）的总数。

示例：

Input
8
60
20
50
10
40
10
50
30
1
1
1
2
2
3
4
Output
0
1
0
1
0
0
0
0

这是我的代码，但在最坏的情况下，它必须遍历所有内容，使其复杂度为 O(N^2)。我希望有一个更优化的解决方案来降低复杂性。

import sys
from collections import deque

def calculate(N, values, relations):
    tree = {i: [] for i in range(1, N + 1)}
    for i, parent in enumerate(relations, start=2):
        tree[parent].append(i)

    result = [0] * N

    for i in range(1, N + 1):
        stack = deque([(i, values[i - 1])]) 
        while stack:
            node, parent_value = stack.pop()
            for child in tree[node]:
                if values[child - 1] > parent_value:
                    result[i - 1] += 1
                stack.append((child, parent_value))

    return result

N = int(sys.stdin.readline())
values = [int(sys.stdin.readline()) for _ in range(N)]
relations = [int(sys.stdin.readline()) for _ in range(N - 1)]

for result in calculate(N, values, relations):
    print(result)

Answer 1

您是正确的，您当前的算法的最坏情况时间复杂度为 O(N^2)，这对于大 N 来说并不理想。以下是一些提高复杂度的方法： *优化遍历。 *利用记忆。 *改善亲子关系表征。 *预处理数据。 看看是否有任何方法有效并解决您的问题。