Python से सबट्री में समान लेबल वाले नोड्स की संख्या कैसे ढूंढें?

रूटेड ट्री में प्रत्येक नोड के लिए, उसके सबट्री में उसी लेबल वाले नोड्स की संख्या ढूंढें (लेबल्स लोअरकेस लेटर्स)।

एल्गोरिदम

• एज लिस्ट से ग्राफ बनाएं (अनडायरेक्टेड)।
• नोड->लेबल मैप बनाएं।
• रिकर्सिव DFS r(ni): चिल्ड्रन के काउंटर्स मर्ज करें, अपना लेबल जोड़ें, R[ni] = count[label]।
• पैरेंट लिंक हटाकर साइकिल अवॉइड करें।

उदाहरण कोड

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" -> [3,2,1,1,1]

इनपुट/आउटपुट

इनपुट: n=5, edges=[[0,1],[0,2],[1,3],[0,4]], labels="ccaca"
आउटपुट: [3, 2, 1, 1, 1]