Giả sử chúng ta có một cây tổng quát gốc với n nút, các nút của chúng được đánh số từ 0 đến n-1. Mỗi nút có một nhãn với chữ cái tiếng Anh viết thường. Các nhãn được đưa ra dưới dạng đầu vào trong mảng nhãn, trong đó nhãn [i] chứa nhãn cho nút thứ i. Cây được biểu diễn bằng danh sách cạnh trong đó mỗi cạnh e có [u, v] đại diện cho u là cha và v là con. Chúng ta phải tìm một mảng A có kích thước n, đại diện cho số nút trong cây con của nút thứ i có cùng nhãn với i
Vì vậy, nếu đầu vào giống như
Đây là n =5 và label =“ccaca”
thì đầu ra sẽ là [3, 2, 1, 1, 1] vì nút gốc có ba nút con có cùng nhãn, nút 1 có hai nút con và tất cả các nút khác tự giữ nhãn đó.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
E:=Tạo đồ thị từ danh sách cạnh đã cho
-
N:=một bản đồ chứa mỗi số nút và nhãn tương ứng của nó
-
R:=danh sách kích thước n và điền bằng 0
-
Định nghĩa một hàm r (). Điều này sẽ mất ni
-
C:=một bản đồ để lưu giữ tần số của một khóa
-
đối với mỗi e trong E [ni], hãy thực hiện
-
xóa ni khỏi E [e]
-
cập nhật r (e) trong C
-
-
cập nhật N [ni] trong C
-
R [ni]:=C [N [ni]]
-
trả lại C
-
Từ phương thức chính, hãy gọi r (0)
-
trả lại R
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
5, [[0,1],[0,2],[1,3],[0,4]], "ccaca"
Đầu ra
[3, 2, 1, 1, 1]