+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فرض کنید یک درخت دودویی با ارتفاع $h$ و تعداد $2h$ گره برگ داریم. هر گره درخت نیز دارای یک مقدار می‌باشد. تعریف می‌کنیم: + اگر گره $x$ برگ باشد، $\alpha (x)$ برابر است با مجموعه شامل گره $x$ و اجدادش تا ریشه درخت.(به همراه ریشه درخت) + اگر $x$ و $y$ دو گره مجزا باشند، $\alpha (x,y)$ برابر است با اجتماع $\alpha (x)$ و $\alpha (y)$ + تابع $f(x,y)$ حاصل جمع عناصر $\alpha (x,y)$ را می‌دهد. الگوریتمی ارائه دهید که برای یک درخت دودویی کامل دو گره برگ $x^\*$ و $y^\*$ را که مقدار $f(x^\*, y^\*)$ برای آن‌ها حداکثر است را پیدا کند و $f(x^\*, y^\*)$ را به عنوان خروجی برگرداند. # ورودی یک عدد $m$ که تعداد نمونه‌های مسئله را بیان می‌کند. سپس $2m$ رشته که با زیر رشته `pre:` و یا `post:` شروع می‌شوند و هرکدام نشان‌دهنده‌ی دنباله‌ی `prefix` و یا `postfix` نمونه خود می‌باشند. $$ 1 \le m \le 6$$ # خروجی برای هر نمونه ورودی یک عدد که نشان‌دهنده‌ی $f(x^*,y^*)$ می‌باشد. # مثال ## ورودی نمونه ``` 1 pre: 36, 21, 15, 10, 19, 30, 20, 14, 6, 11, 5, 9, 10, 2, 7 post: 10, 19, 15, 20, 14, 30, 21, 5, 9, 11, 2, 7, 10, 6, 36 ``` ## خروجی نمونه ``` 141 ```