মান লাগিয়ে, আমাদের একটি রুটেড জেনারেল ট্রি আছে n নোড সহ, যেসব নোড 0 থেকে n-1 পর্যন্ত নম্বর দেওয়া আছে। প্রতিটি নোডের একটি লেবেল আছে লোয়ারকেস ইংলিশ লেটার। লেবেলগুলো labels অ্যারে-তে দেওয়া আছে, যেখানে labels[i] হল i-তম নোডের লেবেল। ট্রিটি একটি এজ লিস্ট দিয়ে রিপ্রেজেন্ট করা আছে যেখানে প্রতিটি edge e = [u,v] মানে u পেরেন্ট এবং v চাইল্ড। আমাদের n আকারের একটি অ্যারে A বের করতে হবে, যা i-তম নোডের সাব-ট্রিতে i-র লেবেলের মত নোড সংখ্যা রিপ্রেজেন্ট করে।
যেমন, ইনপুট যদি এমন হয়:
এখানে n = 5 এবং label = "ccaca"
তবে আউটপুট হবে [3, 2, 1, 1, 1] কারণ রুটের তিনটি ডিসেন্ডেন্ট একই লেবেলে, নোড ১-এর দুটি ডিসেন্ডেন্ট, এবং বাকিগুলো নিজের লেবেল ধারণ করে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- E := দেওয়া এজ লিস্ট থেকে গ্রাফ বানান
- N := প্রতিটি নোড নম্বর এবং তার লেবেল ধারণকারী একটি ম্যাপ
- R := আকার n-এর একটি লিস্ট, ০ দিয়ে ভরা
- একটি ফাংশন r() ডিফাইন করুন। এটি ni নেবে:
- C := কী ফ্রিকোয়েন্সি ধারণকারী একটি ম্যাপ
- E[ni]-এ থাকা প্রতিটি e জন্য:
- E[e]-তে থেকে ni ডিলিট করুন
- 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]
