یک درخت دودویی با $n$ برگ داریم. روی هر یک از برگ‌ها یک رشته به طول $m$ با حروف $\{1,2,3,4\}$ نوشته شده است. ما می‌خواهیم روی راس‌های درونی درخت رشته‌های به طول $m$ بنویسیم به طوری که مجموع کل فاصله‌های رشته هر راس با رشته پدرش کمینه شود. در حالت کلی یک الگوریتم از $Ο(mn)$ ارائه دهید که با گرفتن رشته‌های مربوط به برگ‌ها و ساختار درخت رشته‌های بهینه برای رؤوس درونی درخت را بدست آورد. دقت کنید درخت دودویی درختی است که هر راس آن یا برگ است یا دو فرزند دارد. بعنوان نمونه در شکل زیر یک درخت و جواب آن آمده است. در این درخت $6$ یال وجود دارد که هزینه سه یال $1$ و هزینه بقیه یال‌ها صفر می باشد.

• سوال بعد
• سوال قبل