使用Python程序查找子树中具有相同标签节点的数量

假设我们有一棵有n个节点的有根通用树，每个节点都有带小写英文字母的标签。 标签以labels数组的形式输入，其中lables [i]包含第i个节点的标签。 树由边列表表示，其中每个边缘e具有[u，v]表示u是父节点，v是子节点。 我们必须找到一个大小为n的数组A，表示具有与i相同标签的子树的第i个节点中节点的数量。

因此，如果输入为

这里n = 5，label =“ccaca”

那么输出将是[3，2，1，1，1]，因为根有三个带有相同标签的后代，节点1有两个后代，并且所有其他节点本身都有该标签。

为了解决这个问题，我们将按照以下步骤进行-

• E：从给定的边列表创建图表

• N：包含每个节点编号及其相应标签的映射

• R：大小为n的列表，并用0填充

• 定义r()函数。 这将取ni

• C：用于保存键的频率的映射

• 对于E [ni]中的每个e，请执行以下操作-

  • delete ni from E [e]

  • 在C中更新r（e）

• 在C中更新N [ni]

• R [ni]：= C [N [ni]]

• 返回C

• 从主方法调用r(0)

• 返回R

让我们看以下实现以获得更好的理解-

更多Python相关文章，请阅读：Python 教程

示例

 from collections import defaultdict，Counter
def solve（n，edges，labels）：
  E = defaultdict（set）
  for f，t in edges：
     E [f] .add（t）
     E [t] .add（f）
  N = {i:e for i，e in enumerate（labels）}
  R = [0]* n
  def r（ni）：
     C = Counter（）
     for e in E[ni]：
        E [e] .remove（ni）
        C.update（r（e））
     C.update（（N [ni]））
     R [ni] = C [N [ni]]
     return C
  r（0）
  return R
n = 5
edges = [[0,1]，[0,2]，[1,3]，[0,4]]
labels = “ccaca”
print（solve（n，edges，labels））

输入

5，[[0,1]，[0,2]，[1,3]，[0,4]]， “ccaca”

输出

[3，2，1，1，1]