মান লিজিয়ে আমাদের একটি ট্রি আছে n নোড দিয়ে যা ০ থেকে n-1 পর্যন্ত নম্বরড। ট্রিটি প্যারেন্ট অ্যারে দিয়ে দেওয়া আছে, যেখানে parent[i] হল নোড i-এর প্যারেন্ট। ট্রির রুট হল নোড ০। আমাদের একটি দেওয়া নোডের k-তম পূর্বপুরুষ বের করতে হবে, যদি পূর্বপুরুষ না থাকে তবে -1 রিটার্ন করুন।
যেমন, ইনপুট হলে (চিত্র দেখুন), তবে আউটপুট হবে 2 কারণ নোড ৬-এর প্রথম পূর্বপুরুষ ৫ এবং দ্বিতীয় পূর্বপুরুষ ২।
সমাধানের ধাপসমূহ
solve(parent, node, k)ফাংশন ডিফাইন করুন।যদি
node == -1হয়, তবে-1রিটার্ন করুন।অন্যথায় যদি
k == 1হয়, তবেparent[node]রিটার্ন করুন।অন্যথায় যদি
(k & (k-1)) == 0হয় (অর্থাৎk২-এর ঘাত), তবে:solve(parent, solve(parent, node, k//2), k//2)রিটার্ন করুন।
অন্যথায়,
msb := 1 << (k.bit_length() - 1)solve(parent, solve(parent, node, k-msb), msb)রিটার্ন করুন।
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন:
def solve(parent, node, k):
if node == -1:
return -1
elif k == 1:
return parent[node]
elif not (k & (k-1)):
return solve(parent, solve(parent, node, k >> 1), k >> 1)
else:
msb = 1 << (k.bit_length() - 1)
return solve(parent, solve(parent, node, k - msb), msb)
parent = [-1, 0, 0, 1, 2, 2, 5, 5]
node = 6
k = 2
print(solve(parent, node, k))ইনপুট
[6,7,9,16,22], 2
আউটপুট
2
