Lowest Common Ancestor

در یک درخت ریشه دار ، "پایین ترین جد مشترک" دو گره را دورترین راس از ریشه تعریف می کنیم که جد هردو گره باشد .

این مساله معمولا برای درخت های بزرگ مثلا 10⁵ راسی مطرح میشود .

برای حساب کردن ( 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 .

ایده کلی ساختمان داده اینه که برای هر گره ، 2⁰ امین پدر ، 2¹ امین پدر ، 2² امین پدر و ... رو نگه داریم .

حالا برای بدست آوردن k امین پدر یک گره کافیه k رو به صورت باینری نگاه کنیم .

از اونجایی که k = 2ⁱ₁ + 2ⁱ₂ + ... + 2ⁱ_n  می تونیم

اول 2ⁱ₁ امین پدر k رو محاسبه کنیم سپس پدر k - 2ⁱ₁ گره جدید رو محاسبه کنیم .

از اونجایی که یه عدد رو میشه به صورت حداکثر 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 یعنی پدر 2^j ام از گره i .

اول پدر همه رو -1 می زاریم ، یعنی اینکه هیچ پدری نداره .
بعد پدر سطح 2⁰ ام رو مشخص می کنیم .

حالا چون به ترتیب از پایین به بالا حرکت می کنیم ، برای برست آوردن پدر 2^j ام از راس i کافیه ،

پدر 2^j-1 از راس i رو بدست بیاریم ( قبلا محاسبه کردیم و تو خونه [Tree[i][j-1 ذخیره کردیمش ) و بعد پدر 2^j-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];
}

پیچیدگی زمانی:

( O( N * Log N برای پیش محاسبات و ساختن درخت

( O( Log N برای بدست آوردن هر Query

حافظه : ( O( N * Log N