สมมติว่าเรามีต้นไม้ทั่วไปที่รูทแล้วซึ่งมี n โหนด ซึ่งโหนดมีหมายเลขตั้งแต่ 0 ถึง n-1 แต่ละโหนดมีป้ายกำกับพร้อมตัวอักษรภาษาอังกฤษตัวพิมพ์เล็ก ป้ายกำกับจะได้รับเป็นอินพุตในอาร์เรย์ป้ายกำกับ โดยที่ lables[i] มีป้ายกำกับสำหรับโหนด ith ต้นไม้ถูกแทนด้วยรายการขอบ โดยแต่ละขอบ e มี [u,v] แทน u คือพาเรนต์ และ v เป็นเด็ก เราต้องหาอาร์เรย์ A ขนาด n แทนจำนวนโหนดในทรีย่อยของโหนด ith ที่มีป้ายกำกับเดียวกับ i
ดังนั้นหากอินพุตเป็นแบบ
ที่นี่ n =5 และ label =“ccaca”
จากนั้นผลลัพธ์จะเป็น [3, 2, 1, 1, 1] เนื่องจากรูทมีผู้สืบทอดสามคนที่มีป้ายกำกับเดียวกัน โหนด 1 มีทายาทสองคน และตัวอื่นๆ ทั้งหมดเองที่มีป้ายกำกับนั้น
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
E :=สร้างกราฟจากรายการขอบที่กำหนด
-
N :=แผนที่ที่มีแต่ละหมายเลขโหนดและป้ายกำกับที่เกี่ยวข้อง
-
R :=รายการขนาด n และเติม 0
-
กำหนดฟังก์ชัน r() นี่จะใช้เวลา ni
-
C :=แผนที่เก็บความถี่ของคีย์
-
สำหรับแต่ละอีใน E[ni] ทำ
-
ลบ ni จาก E[e]
-
อัปเดต r(e) ใน C
-
-
อัปเดต N[ni] ใน C
-
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]
