رستوران آقای خرچنگ دارای $n$ آشپز است که با اعداد ۱ تا $n$ شمارهگذاری شدهاند. هر آشپز $i$ (بجز شمارهی ۱ که سرآشپز است) یک آشپز ناظر مستقیم دارد که شمارهی آن $p_i$ است. آشپز شمارهی $i$ ناظر کلی آشپز شمارهی $j$ است، اگر و تنها اگر ناظر مستقیم او یا ناظر کلی آشپز $p_j$ باشد. همچنین حقوق آشپز شمارهی $i$ برابر $w_i$ است.
آقای خرچنگ به تازگی ورشکسته شده است برای همین قصد دارد تا نیروهای رستوران خود را تعدیل کند. او این کار را در دو مرحله انجام میدهد:
آقای خرچنگ به شما اعتماد کرده تا بهترین تعدیل نیرو را انجام دهید، ولی شما از پلانکتون پول زیادی گرفتهاید تا به ازای هر انتخاب سرآشپز در مرحلهی اول، انتخابی را در مرحلهی دوم انجام دهید که آقای خرچنگ بیشترین میانگین حقوق را پرداخت کند و این مقدار را خروجی دهید.
خط اول شامل عدد $n$ است که نشاندهندهی تعداد آشپزهاست.
خط دوم شامل $n$ عدد است که با فاصله از هم جدا شدهاند و عدد $i$اُم نشاندهندهی مقدار $w_i$ است.
خط سوم شامل $n-1$ عدد است که با فاصله از هم جدا شدهاند و عدد $i$اُم نشاندهندهی $p_{i+1}$ است.
خروجی شامل $n$ خط است. در خط $i$اُم خروجی اگر مقدار جواب به ازای انتخاب آشپز $i$ به عنوان سرآشپز جدید برابر با $ans_i$ باشد، باید به ترتیب دو عدد $P_i$ و $Q_i$ را خروجی دهید که $ans_i = \frac{P_i}{Q_i}$ و $\gcd(P_i,Q_i) = 1$ است. به ازای هر $i$ که $ans_i = 0$ بود، مقادیر $P_i=0$ و $Q_i=1$ را درنظر بگیرید.
به ازای هر زیرمسئله، اگر خروجی شما برای آشپز شماره ۱ (همان سرآشپز اولیه) درست باشد ۲۰٪ نمرهی زیرمسئله را دریافت میکنید.
| ورودی نمونه | خروجی نمونه |
|---|---|
5 5 5 0 10 2 1 2 2 4 | 20 3 15 2 0 1 10 1 2 1 |