المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲۴:سوال ۳

GCDTree

درختی ریشه‌دار در نظر بگیرید که روی راس شماره‌ی $i$ عدد $a_i$ نوشته شده است. $f_i$ برابر است با تعداد زوج راس‌های نسبت به هم اول در زیردخت راس $i$. به طور دقیق‌تر $f_i$ مساوی است با تعداد زوج‌هایی مانند $(j,k)$ به طوری که $j<k$ باشد، راس‌های $j$ و $k$ در زیردرخت راس $i$ باشند و هم‌چنین اعداد $a_j$ و $a_k$ نسبت به هم اول باشند. دقت کنید که راس $i$ نیز در زیردرخت خودش قرار دارد.

برنامه‌ای بنویسید که درختی را به عنوان ورودی بگیرد و دنباله‌ی $f_i$ ها را برای آن محاسبه کند.

ورودی

در سطر اول ورودی عدد طبیعی $n$، تعداد راس‌های درخت، آمده است.($1\leq n \leq 10^5$)

سطر دوم شامل $n$ عدد طبیعی است که دنباله‌ی $a_1,a_2,…,a_n$ را نشان می‌دهند.($1\leq a_1,a_2,…,a_n\leq 6\times 10^6$)

سطر سوم شامل دنباله‌ی $p_1,p_2,…,p_n$ است که $p_i$ نشان‌گر شماره‌ی پدر راس $i$ است. پدر راس رریشه، صفر در نظر گرفته می‌شود.($0\leq p_1,p_2,…,p_n\leq n$)

خروجی

در تنها سطر خروجی $n$ عدد چاپ کنید که دنباله‌ی $f_1,f_2,…,f_n$ مربوط به درخت ورودی را نشان می‌دهد.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5
4 2 1 3 6
0 1 1 3 3
6 0 2 0 0
4
4 3 2 1
2 3 4 0
0 1 2 5
10
6 7 10 14 10 5 29 6 17 21
0 4 10 1 10 4 1 4 7 1
28 0 0 4 0 0 1 0 0 2

ابزار صفحه