Python을 사용하여 동일한 레이블을 가진 하위 트리의 노드 수를 찾는 프로그램

노드가 0에서 n-1까지 번호가 매겨진 n개의 노드가 있는 루트 일반 트리가 있다고 가정합니다. 각 노드에는 소문자 영어로 된 레이블이 있습니다. 레이블은 레이블 배열의 입력으로 제공되며, 여기서 lables[i]는 i번째 노드에 대한 레이블을 포함합니다. 트리는 각 에지 e가 [u,v]를 갖고 u가 부모이고 v가 자식을 나타내는 에지 목록으로 표시됩니다. i

따라서 입력이 다음과 같으면

여기서 n =5 및 레이블 ="ccaca"

루트에는 동일한 레이블을 가진 3개의 자손이 있고 노드 1에는 2개의 자손이 있으며 나머지는 모두 해당 레이블을 보유하므로 출력은 [3, 2, 1, 1, 1]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• E :=주어진 에지 목록에서 그래프 만들기

• N :=각 노드 번호와 해당 레이블을 포함하는 맵

• R :=크기가 n이고 0으로 채워진 목록

• r() 함수를 정의합니다. 시간이 걸립니다

• 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]