====== سوال ۴ ======


یک درخت ریشه دار ‎$n$‎ رأسی، درختی ‎ $n$‎رأسی است که یک رأس آن، به عنوان ریشه مشخّص شده‌است. عمق یک رأس در یک درخت
ریشه‌دار ‎(کوتاه‌ترین)‎ فاصله‌ی آن رأس تا ریشه است.

یک روز افشین تصمیم می‌گیرد از روی درخت‌های ریشه دار ‎$n$‎ رأسی، رشته‌هایی به طول ‎$2n-2$‎ از صفر و یک بسازد. 
او برای ساختن یک رشته از روی یک درخت ریشه‌دار، با یک رشتهٔ تهی شروع کرده و به این صورت عمل می‌کند که 
ریشه را رنگ کرده و بقیهٔ رئوس را بدون رنگ در نظر می‌گیرد. سپس از ریشه شروع کرده و در هر مرحله اگر در رأس ‎$v$‎ بود:
  * اگر ‎$v$‎ حداقل یک همسایه‌ی رنگ نشده داشت، یکی از همسایه‌های بی‌رنگ آن را به دل‌خواه انتخاب می‌کند، آن همسایه را رنگ می‌کند و به آن همسایه (می‌‎توان اثبات کرد که این همسایه، الزاماً عمقش یک واحد بیش‌تر از ‎$v$‎‎ است) می‌رود. (یعنی مرحله‌ی بعد، الگوریتم از این رأس اجرا می‌شود) هم‌چنین به انتهای رشته، عدد ‎$1$‎ را اضافه می‌کند.
  * اما اگر همه‌ی همسایه‌های ‎$v$‎ رنگ‌دار بودند، در این صورت اگر ‎$v$‎ ریشه بود، الگوریتم به پایان می‌رسد. وگرنه، به پدر ‎$v$ (تنها همسایه‌ای که عمقش از ‎$v$‎ یک واحد کم‌تر است (‎در واقع همان رأسی که ازش آمده‌ایم) می‌رود. (یعنی مرحله‌ی بعد، الگوریتم از این رأس اجرا می‌شود) هم‌چنین به انتهای رشته، عدد ‎$0$‎ را اضافه می‌کند.

برای مثال یک مسیر به طول سه که یک رأس غیر انتهایی آن به عنوان ریشه انتخاب شده (مطابق شکل)، {{:سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۱۷:الگوریتم‌ها:trie.png?200 |}}
یک درخت ریشه‌دار چهاررأسی است که فقط دو رشتهٔ ‎$101100$‎ و ‎$110010$‎ از 
روی آن ساخته می‌شوند.
‎


صبح امروز افشین دو رشته‌ی ‎$S_1$‎ و ‎$S_2$‎ به‌طول ‎$2n-2$‎ از صفر و یک به شما داده و ادعا می‌کند که این ‎$2$‎ رشته را از روی دقیقاً یک درخت ساخته است.
الگوریتمی از ‎${\cal O}(n^2\lg{n})$‎ بدهید که با گرفتن ‎$S_1$‎ و ‎$S_2$‎، 
مشخص کند که ‎«آیا درخت ریشه‌داری وجود دارد که هر دو این رشته‌ها بتوانند از روی آن ساخته شوند یا نه؟»‎ 
برای مثال این الگوریتم برای رشته‌های ‎$110010$‎ و ‎$101100$‎ باید جواب ‎«صحیح»‎ و برای رشته‌های ‎$110010$‎ و ‎$111000$‎ باید جواب ‎«غلط»‎ را برگرداند.

الگوریتم خود را تحلیل و اثبات کنید.

  * [[سوال ۵|سوال بعد]]
  * [[سوال ۲|سوال قبل]]