====== درخت دودویی جست‌وجو ====== $n$ عدد صحیح در یک درخت دودویی جست‌و‌جو درج شده‌اند. متاسفانه به علت نامشخصی این اعداد از درخت دودویی جست‌وجو پاک شده‌اند اما خوشبختانه ساختار درخت و اعداد را در اختیار داریم. شما باید برنامه‌ای بنویسید که برای گره خاص از درخت، عددی که قبل از پاک شدن در آن ذخیره شده بود را پیدا کند. ===== ورودی ===== سطر اول ورودی شامل عدد طبیعی $n$ ($1\leq n \leq 1000$) است که بیانگر تعداد گره‌های درخت دودویی یا به عبارتی تعداد اعداد می‌باشد. به هر گره درخت یک شماره بین ۱ تا $n$ نسبت داده شده است و گره $nil$ را با عدد ۰ می‌شناسیم. از سطر دوم تا سطر $n+1$، در هر سطر سه عدد صحیح $a\quad b\quad c$ (از چپ به راست) قرار گرفته‌اند که $1\leq a \leq n$ و $0 \leq b,c \leq n$ می‌باشد که در آن $b$ و $c$ به ترتیب فرزند چپ و فرزند راست گره $a$ می‌باشند. از سطر $n+2$ تا سطر $2n+1$، در هر سطر یک عدد صحیح قرار گرفته است و در سطر آخر یک عدد بین ۱ تا $n$ قرار دارد که شماره گره‌ای است که قرار است عدد ذخیره شده در آن پیدا شود. ===== خروجی ===== خروجی شامل یک سطر است. اگر درخت ورودی درست نباشد(ساختار درختی نداشته باشد و یا تعداد عناصر آن درست نباشد) در خروجی عبارت ''Tree is not OK'' چاپ شودو اگر درخت درست بود شامل عدد صحیحی است که در داخل گره خواسته شده قرار می‌گیرد. ===== محدودیت‌ها ===== * محدودیت زمان: ۵ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |4 \\ 3 1 2 \\ 1 0 0 \\ 2 0 4 \\ 4 0 0 \\ 12 \\ 8 \\ 25 \\ 17 \\ 2 | 17| * [[سوال ۱۲|سوال بعد]] * [[سوال ۱۰|سوال قبل]]