المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۴۱

Tree

در پی اینکه دانش‌پژوه‌نمایی به نام ع.ط. در اقدامی به دور از ادب بدون اجازه وارد اتاق سرور شد، مسئولین تصمیم گرفتند او را به جایی دور تبعید کنند. در این جای دور تعدادی خانه وجود دارد که نقشه‌ی همسایگی آن‌ها یک درخت است. در ابتدا ما او را به خانه‌ی یک تبعید کرده‌ایم. او که تبحر خاصی در بی‌اجازه وارد خانه‌ی مردم شدن دارد می‌تواند هر ثانیه بدون اجازه به یکی از خانه‌های همسایه برود.

در هر مرحله به او می‌گوییم بی‌اجازه به سمت خانه‌ی $v$ حرکت کن هم‌چنین برای اینکه اندکی او را اذیت کنیم، همان‌طور که او در حال رفتن به سمت $v$ است (و یا به $v$ رسیده است) بعد از $t$ ثانیه می‌گوییم مقصدت را عوض کن و به سمت خانه‌ی $u$ شروع به حرکت کن. در هربار که ما دستور جدیدی به او می‌دهیم او اعلام می‌کند در چه خانه‌ای است و سپس به سمت مقصد جدید به راه می‌افتد.

ورودی

  • در سطر اول ورودی دو عدد $n$ و $m$ آمده‌اند.
  • در هر یک از $n-1$ سطر بعد دو عدد $u$ و $v$ آمده‌است که نشان‌دهنده‌ی وجود یک راه(یال) بین خانه‌ی $u$ و خانه‌ی $v$ است.
  • سپس در هر یک از $m$ سطر بعد، یک دستور به صورت $t$ $v$ ‌آمده است یعنی $t$ ثانیه بعد از دستور قبلی به او می‌گوییم جهت حرکت خود را را به سمت خانه‌ی $v$ تغییر بده.

خروجی

در $m$ سطر، خانه‌ای که او در لحظه‌ی دستور فعلی در آن قرار دارد را چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
4 3
1 2
2 3
3 4
1 4
2 1
100 4
1
3
4

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه