Pythonを使用して、同じラベルを持つサブツリー内のノードの数を見つけるプログラム

ノードに0からn-1までの番号が付けられたn個のノードを持つルート化された一般ツリーがあるとします。各ノードには、小文字の英字のラベルがあります。ラベルはlabels配列の入力として指定されます。ここで、lables[i]にはi番目のノードのラベルが含まれています。ツリーはエッジリストで表され、各エッジeには[u、v]があり、uは親、vは子を表します。サイズnの配列Aを見つける必要があります。これは、iと同じラベルを持つi番目のノードのサブツリー内のノードの数を表します

したがって、入力が次のような場合

ここで、n =5およびlabel=“ ccaca”

ルートには同じラベルの子孫が3つあり、ノード1には子孫が2つあり、他のすべての子孫がそのラベルを保持しているため、出力は[3、2、1、1、1]になります。

これを解決するには、次の手順に従います-

• E：=指定されたエッジリストからグラフを作成する

• N：=各ノード番号とそれに対応するラベルを含むマップ

• R：=サイズnのリストで、0で埋めます

• 関数r（）を定義します。これにはniがかかります

• C：=キーの頻度を保持するためのマップ

• E [ni]の各eについて、実行

  • E [e]

    からniを削除します

  • Cでr（e）を更新する

• C

  でN[ni]を更新します

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

• Cを返す

• メインメソッドからr（0）を呼び出します

• Rを返す

理解を深めるために、次の実装を見てみましょう-

例

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]