โปรแกรมนับโหนดใน Subtree ที่มี Label เหมือน Root ด้วย Python

Tree n โหนด มี label ตัวอักษร หาแต่ละโหนด i: จำนวนโหนดใน subtree ของ i ที่มี label เหมือน i ใช้ DFS post-order สร้าง graph จาก edges DFS คืน Counter ของ labels ใน subtree รวม label ของตัวเอง แล้ว R[i] = count ของ label i

ขั้นตอนการทำงาน

1. สร้าง adjacency list E จาก edges
2. N = map โหนด -> label
3. R = [0]*n ผลลัพธ์
4. DFS r(ni): C = Counter(), สำหรับ child e ใน E[ni]: ลบ ni ออกจาก E[e], C.update(r(e))
5. C.update(N[ni]), R[ni] = C[N[ni]], return C
6. เรียก 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))  # Output: [3, 2, 1, 1, 1]

อินพุต/เอาต์พุต

Input: n=5, edges=[[0,1],[0,2],[1,3],[0,4]], labels="ccaca"
Output: [3, 2, 1, 1, 1]

โหนด 0 (c) มี subtree labels: c,c,a,c,a -> 3 c's; โหนด 1 (c) มี c,c,a -> 2 c's; โหนดอื่นๆ มีแค่ตัวเอง