سوال ۴

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

یک روز افشین تصمیم می‌گیرد از روی درخت‌های ریشه دار $n$ رأسی، رشته‌هایی به طول $2n-2$ از صفر و یک بسازد. او برای ساختن یک رشته از روی یک درخت ریشه‌دار، با یک رشتهٔ تهی شروع کرده و به این صورت عمل می‌کند که ریشه را رنگ کرده و بقیهٔ رئوس را بدون رنگ در نظر می‌گیرد. سپس از ریشه شروع کرده و در هر مرحله اگر در رأس $v$ بود:

• اگر $v$ حداقل یک همسایه‌ی رنگ نشده داشت، یکی از همسایه‌های بی‌رنگ آن را به دل‌خواه انتخاب می‌کند، آن همسایه را رنگ می‌کند و به آن همسایه (می‌توان اثبات کرد که این همسایه، الزاماً عمقش یک واحد بیش‌تر از $v$ است) می‌رود. (یعنی مرحله‌ی بعد، الگوریتم از این رأس اجرا می‌شود) هم‌چنین به انتهای رشته، عدد $1$ را اضافه می‌کند.
• اما اگر همه‌ی همسایه‌های $v$ رنگ‌دار بودند، در این صورت اگر $v$ ریشه بود، الگوریتم به پایان می‌رسد. وگرنه، به پدر $v$ (تنها همسایه‌ای که عمقش از $v$ یک واحد کم‌تر است (در واقع همان رأسی که ازش آمده‌ایم) می‌رود. (یعنی مرحله‌ی بعد، الگوریتم از این رأس اجرا می‌شود) هم‌چنین به انتهای رشته، عدد $0$ را اضافه می‌کند.

برای مثال یک مسیر به طول سه که‌یک رأس غیر انتهایی آن به عنوان ریشه انتخاب شده (مطابق شکل)، یک درخت ریشه‌دار چهاررأسی است که فقط دو رشتهٔ $101100$ و $110010$ از روی آن ساخته می‌شوند.

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

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