المپدیا

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

ابزار کاربر

ابزار سایت


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

Labels

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

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

ورودی

  • در سطر اول ورودی دو عدد $0 \leq m \leq 100000$ و $1 \leq n \leq 100000$ نشان‌دهنده تعداد رئوس و تعداد پرسمان‌ها آمده است.
  • در $n-1$ سطر بعدی، در هر سطر دو عدد $1 \leq u_i, v_i \leq n, u_i \neq v_i$ آمده است كه یال‌های درخت را مشخص می‌كند.
  • در سطر بعدی یک رشته به طول $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

ابزار صفحه