المپدیا

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

ابزار کاربر

ابزار سایت


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

karaks

کشور کرکس‌آباد‎‎ از ‎$n$‎ شهر تشکیل شده که توسط ‎$n-1$‎ جاده به هم متصل شده‌اند، به طوری که با استفاده از این جاده‌ها می‌توان از هر شهری به هر شهر دیگری سفر کرد. فاصله دو شهر ‎$x$‎ و ‎$y$‎ در کرکس‌آباد، برابر تعداد جاده‌هایی است که برای رفتن از شهر ‎$x$‎ به شهر ‎$y$‎ باید از آنها عبور کرد.

امسال $‎$100‎امین سال تأسیس کشور کرکس‌آباد است و کرکس بزرگ (پادشاه کرکس‌آباد) دستور داده تا جشن بزرگی برگزار شود. مسئولیت مراسم آتش‌بازی را به ملکه‌ی کرکس‌آباد، شیکرکس‎‎ سپرده است. طبق برنامه‌ریزی شیکرکس، مراسم آتش‌بازی در ‎$ q $‎ شب برگزار می‌شود و آتش‌بازی شب ‎$i$‎ام را شهر ‎$v_i$‎ برگزار می‌کند. متأسفانه شیکرکس به جای خرید مواد آتش‌بازی مرغوب، مواد چینی خریداری کرده و این مواد دارای اشکال هستند، و زمانی که آتش‌بازی در شهر ‎$x$‎ اجرا می‌شود، مراسم فقط در شهرهایی قابل مشاهده است که دقیقاً‎ در فاصله ‎$k$‎ از شهر ‎$x$‎ قرار دارند.

کرکس بزرگ که از بی‌مسئولیتی شیکرکس عصبانی شده، به او دستور داده که سریعاً محاسبه کند هر شهر در چند شب می‌تواند مراسم آتش‌بازی را مشاهده کند. اما شیکرکس که با برنامه‌نویسی آشنایی ندارد، نمی‌تواند این کار را انجام دهد و برای همین از شما خواسته تا به او کمک کنید.

ورودی

  • در سطر اول ورودی ‎$n$‎ و ‎$q$‎ و ‎$k$‎ به ترتیب آمده است.‎
  • در هر یک از ‎$n-1$‎ سطر بعدی دو عدد ‎$x$‎ و ‎$y$‎ آمده است که نشان‌دهنده‌ی وجود یک جاده بین شهر ‎$x$‎ و ‎$y$‎ است‎.‎
  • در سطر آخر ‎$q$‎ عدد می‌آید که عدد ‎$i$‎ام نشان‌دهنده‌ی ‎$v_i$‎ است.
  • ‎ در ‎۳۰٪‎ تست‌ها: ‎$ n‎, ‎q \leq 5000$‎
  • ‎ در تمام تست‌ها: ‎$1 \leq n \leq 200000$‎، ‎$q \leq 10 ^ 6$‎ و ‎$0 \leq k \leq 100$‎

خروجی

‎ در تنها سطر خروجی باید ‎$n$‎ عدد چاپ کنید که عدد ‎$i$‎ام آن برابر با تعداد آتش‌بازی‌هایی است که در شهر ‎$i$‎ام قابل مشاهده هستند.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
5 3 2‎
5 3‎
4 5‎
2 5‎
1 5‎
3 4 5
2 2 1 1 0
3 2‎
4 2‎
1 2‎
6 1‎
5 6‎
5 6 3 4
0 1 1 1 0 2


ابزار صفحه