Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

GCDTree

درختی ریشه‌دار در نظر بگیرید که روی راس شماره‌ی i عدد ai نوشته شده است. fi برابر است با تعداد زوج راس‌های نسبت به هم اول در زیردخت راس i. به طور دقیق‌تر fi مساوی است با تعداد زوج‌هایی مانند (j,k) به طوری که j<k باشد، راس‌های j و k در زیردرخت راس i باشند و هم‌چنین اعداد aj و ak نسبت به هم اول باشند. دقت کنید که راس i نیز در زیردرخت خودش قرار دارد.

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

ورودی

در سطر اول ورودی عدد طبیعی n، تعداد راس‌های درخت، آمده است.(1n105)

سطر دوم شامل n عدد طبیعی است که دنباله‌ی a1,a2,,an را نشان می‌دهند.(1a1,a2,,an6×106)

سطر سوم شامل دنباله‌ی p1,p2,,pn است که pi نشان‌گر شماره‌ی پدر راس i است. پدر راس رریشه، صفر در نظر گرفته می‌شود.(0p1,p2,,pnn)

خروجی

در تنها سطر خروجی n عدد چاپ کنید که دنباله‌ی f1,f2,,fn مربوط به درخت ورودی را نشان می‌دهد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
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

ابزار صفحه