سوال ۷۷ کنکور ارشد علوم کامپیوتر ۱۴۰۲

$T$ یک درخت ریشه‌دار با ریشه $r$ است و هر رأس $x$ به آن یک وزن $w(x)$ دارد. کدام رابطه بازگشتی منجر به یک الگوریتم پویا (dynamic) برای محاسبه وزن مسیری که از $r$ شروع می‌شود که از $S$ شروع می‌شود و مجموع وزن رأس‌هایش بیشترین مقدار ممکن است؟

(الف) $\begin{cases} F(v) = w(v) & : \text{برای هر برگ } v \\ F(v) = w(v) + \max\limits_{x \text{ فرزند } v} F(x) & : \text{برای هر رأس غیربرگ } v \\ \text{پاسخ} = F(r) \end{cases}$

(ب) $\begin{cases} F(r) = w(r) \\ F(v) = w(v) + F(v \text{ پدر}) \\ \text{پاسخ} = \max\limits_{x \text{ برگ}} F(x) \end{cases}$