در یک درخت ریشه دار ، "پایین ترین جد مشترک" دو گره را دورترین راس از ریشه تعریف می کنیم که جد هردو گره باشد .
این مساله معمولا برای درخت های بزرگ مثلا 105 راسی مطرح میشود .
برای حساب کردن ( LCA( x , y به صورت زیر عمل می کنیم .
بدون کاسته شدن از کلیت فرض کنید گره x در ارتفاع بیشتری باشه .
قبل از هر کاری باید گره x رو اونقدر به بالا منتقل کنیم تا هم ارتفاع با y بشه .
حالا اگر x = y باشه در نتیجه LCA همان x است
اگر x != y باشه ، تو این حالت از اونجاییکه فاصله x تا LCA و فاصله y تا LCA برابر است یک مقدار i دلخواه پیدا می کنیم که i امین پدر x و y با هم برابر نباشند ، از اونجایی که
LCA( x , y ) = LCA( Parent( x , i ) , Parent( y , i ) )
می تونیم قرار بدیم ( x = Parent( x , i ) , y = Parent( y , i و مساله رو برای این زیر مساله حل کنیم .
اگر خوب دقت کنید میبینید که انتخاب i خیلی تو سرعت الگوریتم تاثیر داره .
منظور از ( Parent( x , y یعنی پدر y ام گره x .
ایده کلی ساختمان داده اینه که برای هر گره ، 20 امین پدر ، 21 امین پدر ، 22 امین پدر و ... رو نگه داریم .
حالا برای بدست آوردن k امین پدر یک گره کافیه k رو به صورت باینری نگاه کنیم .
از اونجایی که k = 2i1 + 2i2 + ... + 2in می تونیم
اول 2i1 امین پدر k رو محاسبه کنیم سپس پدر k - 2i1 گره جدید رو محاسبه کنیم .
از اونجایی که یه عدد رو میشه به صورت حداکثر Log N تا جمعوند نوشت ، الگوریتم بعد از Log N محاسبه به جواب می رسه .
نحوه ساختن درخت
برای ساختن درخت کافیه برای هر گره بدونید پدرش کیه و تو چه ارتفاعی قرار داره .
برای این کار می تونید درخت از ریشه BFS یا DFS بزنید تا Dep و Parent هر گره رو معلوم کنید .
حالا با داشتن این مقادیر درخت رو می سازیم
for( int i = 0 ; i < N ; i ++ )
for( int j = 0 ; ( 1 << j ) < N ; j ++ )
Tree[i][j] = -1;
for( int i = 0 ; i < N ; i ++ )
Tree[i][0] = Par[i];
for( int j = 1 ; ( 1 << j ) < N ; j ++ )
for( int i = 0 ; i < N ; i ++ )
Tree[i][j] = Tree[ Tree[i][j-1] ][j-1];
تو این درخت ، منظور از [Tree[i][j یعنی پدر 2j ام از گره i .
اول پدر همه رو -1 می زاریم ، یعنی اینکه هیچ پدری نداره .
بعد پدر سطح 20 ام رو مشخص می کنیم .
حالا چون به ترتیب از پایین به بالا حرکت می کنیم ، برای برست آوردن پدر 2j ام از راس i کافیه ،
پدر 2j-1 از راس i رو بدست بیاریم ( قبلا محاسبه کردیم و تو خونه [Tree[i][j-1 ذخیره کردیمش ) و بعد پدر 2j-1 ام اون گره رو بدست بیاریم ( این مقدار رو هم قبلا محاسبه کردیم )
برای بدست آوردن LCA دو گره کافیه تابع زیر رو فراخوانی کنیم
int LCA( int x , int y ) {
if( Dep[x] < Dep[y] )
swap( x , y );
int log = 0;
for( int log = 0 ; ( 1 << log ) < Dep[x] ; log ++ );
log --;
for( int j = log ; j >= 0 ; j -- )
if( ( Dep[x] - Dep[y] ) & ( 1 << j ) )
x = Tree[x][j];
if( x == y )
return x;
for( int j = log ; j >= 0 ; j -- )
if( Tree[x][j] != -1 && Tree[x][j] != Tree[y][j] )
x = Tree[x][j], y = Tree[y][j];
return Par[x];
}
