Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

Labels

یک درخت n راسی به شما داده شده كه هر كدام از رئوس آن یك برچسب از حروف ’a’ تا ’z’ دارد. شما باید m پرسمان به صورت‌های زیر را اجرا کنید:

برچسب راس 1xn را برابر با ’a’ y ’z’ قرار بده. میانگین فاصله راس x از رئوسی که برچسب آن‌ها ’a’ y ’z’ است را چاپ کن.

ورودی

  • در سطر اول ورودی دو عدد 0m100000 و 1n100000 نشان‌دهنده تعداد رئوس و تعداد پرسمان‌ها آمده است.
  • در n1 سطر بعدی، در هر سطر دو عدد 1ui,vin,uivi آمده است كه یال‌های درخت را مشخص می‌كند.
  • در سطر بعدی یک رشته به طول n از حروف كوچك الفبای انگلیسی آمده است كه كه به ترتیب برچسب روی رئوس شماره 1 تا n را مشخص می‌کند.
  • در هر یک از m سطر یک پرسمان به صورت زیر مطرح شده است:
    • c x y که پرسمان اول را مشخص می‌کند که x یک راس و y یک حرف کوچک الفبای انگلیسی است.
    • a x y که پرسمان دوم را مشخص می‌کند که x یک راس و y یک حرف کوچک الفبای انگلیسی است.

خروجی

به ازای هر پرسمان از نوع دوم، اگر هیچ راسی با برچسب مورد نظر وجود نداشتن عدد 1 را در خروجی چاپ كنید. در غیر صورت پاسخ سوال را به صورت A/B که A و B اعدادی نسبت به‌هم اول هستند چاپ کنید. پاسخ هر پرسمان را در یك سطر جداگانه چاپ نمایید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 7
1 2
2 3
abc
a 1 a
a 1 b
a 1 c
c 1 b
a 1 b
a 2 b
a 2 d
0/1
1/1
2/1
1/2
1/2
-1

ابزار صفحه