DFS Start/Finish Time¶
در این بخش می خواهیم با ترفندی گراف را به آرایه تبدیل کنیم.
ایده های مختلفی وجود دارد که بتوان گراف را به یک آرایه تبدیل کرد که starting time یکی از آن ها است. با استفاده از این ایده می توان گراف داده شده را به آرایه تبدیل کرد و با آن انواع سوال ها را با سادگی بیشتری حل کرد.
می توان برای هر راس اولین زمانی که الگوریتم dfs بر روی آن وارد شده است را در نظر گرفت. به این صورت هر راس عددی یکتا دارد و می توان راس ها را بر حسب این زمان مرتب کرد و به یک آرایه رسید.
فرض کنید آرایه ای که می خواهیم از راس های گراف درست کنیم a[i] باشد و زمانی که الگوریتم dfs وارد راس u می شود برابر st[u] باشد. در این صورت راس u را در خانه st[u] قرار می دهیم یا به عبارتی a[st[u]] = u است.
مشخص است که هر زیر درخت از درخت dfs آن یک بازه از آرایه است.
finishing time هم مانند starting time تعریف می شود با این تفاوت که زمان خارج شدن الگوریتم dfs از راسی را نشان می دهد.
حال به بررسی چند سوال می پردازیم.
چک کردن جد و نواده بودن در زمان اجرای خطی¶
درخت \(n\) راسی به همراه \(q\) کوئری به ما داده شده. در هر کوئری باید چک کنیم ایا راس \(u\) جد راس \(v\) است یا نه. \(O(n+q)\)
حل¶
از این لم استفاده میکنیم که شرط لازم و کافی برای جد و نواده بودن به این شکل است: \(stt[u]<=stt[v] and fnt[v]<=fnt[u]\) یا \(stt[u]<=stt[v] and stt[v]<fnt[u]\)
به سادگی میتوان درستی این لم را بررسی کرد. پس برای حل مساله ابتدا روی درخت dfs میزنیم و سپس به ازای هر کوئری شرط گفته سده را در \(O(1)\) چک میکنیم.
پیدا کردن kامین پدر¶
درخت \(n\) راسی به همراه \(q\) کوئری به ما داده شده. در هر کوئری باید \(k\) امین پدر راس \(v\) را پیدا کنیم. \(O(n+q.log(n))\)
حل¶
تمام ریوس با ارتفاع \(h[v]-k\) را در نظر بگیرید. با استفاده از لم سوال قبل میتوان نتیجه گرفت جواب راس با بیشترین استارتینگ تایم کمتر از استارتینگ تایم راس \(v\) در بین ریوس در ارتفاع \(k\) تا بالاتر است. به بیان دیگر
- u with maximum stt such that h[u] = h[v] - k and stt[u] <= stt[v]
به ازای هر ارتفاع یک وکتور از تمام ریوس ان ارتفاع بسازید که ریوس هر وکتور بر حسب استارتینگ تایم مرتب شده اند. \(O(n)\)
حال هر کوئری سوال به یک باینری سرچ روی یکی از این وکتور ها تبدیل میشود!
Blood Cousins¶
درخت \(n\) راسی با \(m\) کوئری به شکل v p داده شده. در هر کوئری باید تعداد \(u\) هایی را خروجی دهید که pامین پدر vوu یکسان اند. \(O(n+qlg(n))\)
حل¶
ابتدا pامین پدر راس v را مشابه مساله قبل پیدا کنید. اسم این راس را w بگذارید. حال جواب تعداد u هایی است که \(h[u] = h[v] , stt[w]<=stt[u] , stt[u] < fnt[w]\) . یعنی در وکتور مربوط به راس v تعداد استارتینگ تایم های مربوط به یک بازه را میخواهیم که با باینری سرچ ساده قابل حل است.
دوهمبند کردن با مینیمم تعداد مسیر¶
درخت \(n\) راسی و \(2k\) برگی داده شده. در هر عملیات میتوانیم دو برگ را انتخاب کرده و تمام یالهای مسیر بین ان دو را رنگ کنیم. کمترین تعداد عملیات لازم و یک روش با کمترین تعداد عملیات برای رنگ کردن تمام یالها را پیدا کنید. \(O(n)\)
حل¶
جواب=k در ادامه روش ارایه میدهیم و درستی روش را نشان میدهیم. اگر n=2 سوال بدیهی حل میشود. پس فرض کنید n>2 و حداقل یک راس غیربرگ داریم. از یک راس غیربرگ درخت را ریشه دار کرده و برگ ها را بر حسب استارتینگ تایم شماره گذاری کنید. حال روی این جفت برگ ها عملیات را انجام دهید:
به وضوح پیچیدگی این جفت بندی \(O(n)\) است.
حال باید نشان دهیم همه یالها رنگ میشوند.. زیردرخت هر یال یک بازه از برگها را شامل میشود و برای اینکه یک یال رنگ شود باید جفت برگی داشته باشیم که یک سرش داخل این بازه و سر دیگرش خارج ان باشد. فرض کنید بازه یال مورد نظر \([l, r]\) است. دو حالت را بررسی میکنیم. اول اینکه \(l<=k && k+<=r\) در این حالت اگر \(l!=1\) بود جفت (1, k+1) داخل بازه میافتد. وگرنه جفت (k, 2k) .
اگر بازه متناظر یال مشابه حالت قبل نبود بدون کم شدن کلیت فرض میکنیم \(l,r<=k\) در این حالت هم جفت (r, r+k) این یال را رنگ میکند.
پس در هر دو حالت یال مورد نظر رنگ میشود و جفت هایی که ساختیم معتبراند.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
