الگوریتم پیدا کردن قطر درخت

یکی دیگر از مسائلی که در حالت کلی گراف np است اما در درخت ها به سادگی حل می شود مسئله پیدا کردن بلندترین مسیر است! از آنجایی که در درخت ها مسیر بین هر دو راس یکتا است می توان نتیجه گرفت قطر درخت همان بلندترین مسیر درخت می باشد. در این بخش روش های پیدا کردن قطر درخت را با پیچیدگی زمانی \(O(n)\) بررسی می کنیم.

استفاده از dp

درخت را از راس 1 ریشه دار کنید. با استفاده از برنامه نویسی پویا دو متغیر زیر را به ازای هر راس \(u\) به دست می آوریم.

  • مقدار \(dp_u\) برابر است با بیشترین فاصله راس \(u\) با یک راس درون زیردرخت خود \(u\).
  • مقدار \(ans_u\) برابر است با اندازه قطر در زیردرخت \(u\).

واضح است که جواب مسئله برابر است با \(ans_1\). حالا تنها مسئله باقی مانده این است که چگونه این دو متغیر را به دست آوریم.

برای به دست آوردن \(dp_u\) کافی است توجه کنید که در اولین حرکت از \(u\) به یکی از بچه هایش می رویم. پس باید به بچه ای برویم که مقدار \(dp\) آن بیشینه است.

برای به دست آوردن \(ans_u\) حالت بندی کنید که راس \(u\) درون قطر باشد یا نباشد.

  • اگر راس \(u\) درون قطر نباشد مقدار \(ans_u\) برابر با بیشینه \(ans\) بچه های \(u\) خواهد بود زیرا که قطر کاملا درون یکی از بچه ها خواهد بود.
  • در غیر اینصورت اگر راس \(u\) انتهای قطر باشد جواب برابر با \(dp_u\) خواهد بود.
  • در غیر اینصورت راس \(u\) باید وسط یک مسیر باشد. حالت بندی کنید که دو سر آن به کدام یکی از بچه ها برود. اگر به بچه \(a, b\) برود جواب برابر با \(2 + dp_a + dp_b\) خواهد بود. پس کافیست \(a, b\) را دو بچه ای انتخاب کنیم که مقدار \(dp\) آن ها بیشینه است.

در کد زیر در \(mx1, mx2\) به ترتیب راس های با بیشترین \(dp\) را نگه داری می کنیم.

const int maxn = 1e5 + 10;

vector<int> g[maxn];
int dp[maxn], ans[maxn];

void dfs(int u, int par = 0){
   int mx1 = -1, mx2 = -1;
   for(int y : g[u]){
       if(y != par){
           dfs(y, u);
           dp[u] = max(dp[u], 1 + dp[y]);
           ans[u] = max(ans[u], ans[y]);
           if(mx1 == -1 || dp[mx1] < dp[y]){
                mx2 = mx1;
                mx1 = y;
           }
           else if(mx2 == -1 || dp[mx2] < dp[y]){
                mx2 = y;
           }
       }
   }
   ans[u] = max(ans[u], dp[u]);
   if(mx1 != -1 && mx2 != -1){
        ans[u] = max(ans[u], 2 + dp[mx1] + dp[mx2]);
   }
}

پس توانستیم الگوریتمی ارائه دهیم که با پیچیدگی زمانی \(O(n)\) قطر درخت را پیدا می کند.

dfs up/down

گاهی هدف ما به دست آوردن یک متغیر مثل \(dp\) به ازای هر راس درخت است اما حساب کردن مقدار \(dp_u\) نیاز به داشتن مقدار \(dp\) تمام مجاور های راس \(u\) (و نه فقط بچه های \(u\)) دارد.

ساده ترین مثال برای معرفی این تکنیک مسئله پیدا کردن بیشترین فاصله از هر راس است. فرض کنید می خواهیم به ازای هر راس \(u\) خروج از مرکز این راس را داشته باشیم. جواب راس \(u\) را \(ans_u\) بگیرید. برای به دست آوردن جواب یک راس می توان به راحتی درخت را از این ارتفاع آویزان کرد و در \(O(n)\) ارتفاع درخت را حساب کرد. اما آیا می توان مسئله را به ازای تمام راس با هم در \(O(n)\) حل کرد؟

اولین مشکل ما این است که چون حساب کردن جواب یک راس به داشتن جواب مجاور هایش نیاز دارد نمی دانیم که محاسبه را از کجا شروع کنیم!

درخت را از راس \(u\) ریشه دار کنید. شکاندن مسئله به دو بخش می تواند مفید باشد. فرض کنید \(dpDown_u\) برابر است با بیشترین فاصله از راس \(u\) به راسی درون زیردرخت راس \(u\). همچنین \(dpUp_u\) برابر است با بیشترین فاصله از راس \(u\) به راسی خارج از زیردرخت راس \(u\) (یعنی در اولین گام باید به پدر \(u\) برویم). واضح است که جواب راس \(u\) برابر با بیشینه دو عدد \(dpDown_u\) و \(dpUp_u\) است.

همانطور که در قسمت بالا بررسی کردیم \(dpDown_u\) را می توان از روی \(dpDown\) بچه های راس \(u\) حساب کرد.

برای حساب کردن \(dpUp_u\) توجه کنید که بعد از اینکه از \(u\) به پدر \(u\) رفتیم می توانیم دو راه در پیش بگیریم.

  • می توانیم باز هم به بالا برویم. در اینصورت جواب برابر با \(1 + dpUp_{par}\) است(فرض کنید \(par\) پدر راس \(u\) است).
  • می توانیم به پایین برویم یعنی به یکی از برادر های \(u\) مثل \(w\) بریم. سپس باید پایین برویم. در اینصورت جواب برابر با \(2 + dpDown_w\) می باشد.

نکته کلیدی این است که نیاز نیست هر بار تمام برادر های \(u\) را بررسی کنیم که راس با \(dpDown\) بیشینه (همان \(w\) را پیدا کنیم). کافی است به ازای \(par\) تنها یک بار دو بچه ای که \(dpDown\) آن ها بیشینه است را به دست بیاوریم. همواره راس \(w\) یکی از دو بچه \(par\) است که \(dpDown\) آنها بیشینه است. (چرا؟)

پس فهمیدیم که به چه صورت باید متغیر ها را به دست بیاوریم. اما همچنان یک مشکل حل نشده باقی مانده است. به چه ترتیبی باید به دست آوردن مقادیر را انجام دهیم. برای به دست آوردن \(dpDown\) نیاز داریم که مقادیر بچه ها و برای به دست آوردن \(dpUp\) نیاز داریم که مقادیر پدر را داشته باشیم. پس از کدام یک باید شروع کنیم؟

جواب ساده و هوشمندانه است. می توانیم طی دومرحله مقادیر را به دست بیاوریم. یک بار \(dpDown\) ها را با استفاده از dfsDown و سپس \(dpUp\) ها را با استفاده از dfsUp به دست بیاوریم! نکته اینجاست که در dfsDown ابتدا مقدار بچه ها به دست می آیند سپس مقدار راس فعلی. اما در dfsUp ابتدا مقدار پدر به دست می آید سپس مقدار بچه ها از روی پدر به دست می آیند!

توجه کنید که در تابع dfsUp وقتی روی یک راس هستیم فرض کرده ایم که \(dpUp\) آن راس به دست آمده است و سپس \(dpUp\) بچه های آن را به دست می آوریم.

const int maxn = 1e5 + 10;

vector<int> g[maxn];
int dpUp[maxn], dpDown[maxn];

void dfsDown(int u, int par = 0){ // aval bayad in taabe ra ejra konim
    for(int y : g[u]){
        if(y != par){
            dfsDown(y, u);
            dpDown[u] = max(dpDown[u], dpDown[y]+1);
        }
    }
}
void dfsUp(int u, int par = 0){
   int mx1 = -1, mx2 = -1;
   for(int y : g[u]){
       if(y != par){
           if(mx1 == -1 || dpDown[mx1] < dpDown[y]){
                mx2 = mx1;
                mx1 = y;
           }
           else if(mx2 == -1 || dpDown[mx2] < dpDown[y]){
                mx2 = y;
           }
       }
   }
   for(int y : g[u]){
       if(y != par){
            if(y == mx1){
                dpUp[y] = dpUp[u]+1;
                if(mx2 != -1)
                    dpUp[u] = max(dpUp[u], doDown[mx2]+2);
            }
            else{
                dpUp[y] = max(dpUp[u]+1, doDown[mx1]+2);
            }
            dfsUp(y, u);
       }
   }
}

آویزان کردن از مرکز

با تعریف مرکز گراف در قسمت های قبل آشنا شدیم و فهمیدیم که مرکز یک درخت وسط قطر است. در نتیجه اگر طول قطر فرد بود تنها یک مرکز داریم و اگر طول قطر زوج بود دو مرکز داریم.

یک قطر دلخواه از درخت را مثل \(AB\) در نظر بگیرید.

  • اگر طول قطر زوج بود راس وسط مسیر \(AB\) را \(MID\) بنامید.
  • اگر طول قطر فرد بود یال وسط مسیر \(AB\) را \(MID\) بنامید.

حالا همانند شکل درخت را از \(MID\) آویزان کنید. در این قسمت به بررسی ویژگی های جالب این نوع ریشه دار کردن می پردازیم.

اگه اینترنت یارو آشغال باشه این میاد

در ادامه فرض می کنیم که قطر درخت زوج است (و در نتیجه \(MID\) یک راس است). بررسی حالاتی که قطر فرد باشد به صورت مشابه امکان پذیر است. حتی برای جلوگیری از دو بار کاری می توان وسط هر یال یک راس اضافه کرد (در نتیجه طی کردن یک یال در گراف قبل معادل با طی کردن دو یال در گراف جدید است) و سپس از آنجایی که در گراف جدید تمام فاصله ها دو برابر می شوند، قطر گراف جدید نیز زوج خواهد شد.

پس حالا درخت را از راس \(MID\) ریشه دار در نظر میگیریم و همانطور که می بینید اگر مسیر \(A, B\) تا ریشه را در نظر بگیریم با هم اشتراکی نخواهند داشت (به جز در ریشه). همچنین واضح است که ارتفاع راس های \(A, B\) با هم برابر است این ارتفاع را \(H\) بنامید.

لم 2.7.1

اگر ارتفاع راس \(u\) را \(h(u)\) در نظر بگیریم آنگاه مسیری به طول حداقل \(h(u) + H\) وجود دارد که یک سر آن \(u\) است.

زیرا که اگر از \(u\) به ریشه بروید حداکثر با یکی از دو مسیر \(A\) به ریشه و \(B\) به ریشه اشتراک خواهیم داشت پس می توان با ادامه دادن مسیرمان از ریشه به یکی از \(A\) یا \(B\) برویم.

لم 2.7.2

ارتفاع درخت برابر با \(H\) است. زیرا از طرفی دو راس \(A, B\) ارتفاع \(H\) دارند.

حالا فرض خاف کنید که راسی مثل \(u\) باشد که \(h(u) > H\) طبق لم 2.7.1 مسیری به طول \(h(u) + H\) در درخت وجود خواهد داشت که بیشتر از \(2 \times H\) است. از آن جایی که فرض کردیم \(AB\) قطر درخت است پس امکان ندارد که مسیری بیشتر از \(2 \times H\) در درخت وجود داشته باشد که با فرض خلف در تناقض است و در نهایت ثابت می کند که ارتفاع درخت برابر با \(H\) است.

از کنار هم گذاشتن لم 2.7.1 و لم 2.7.2 نتیجه می شود که خروج از مرکز هر راس مثل \(u\) برابر با \(h(u) + H\) می باشد یعنی فاصله راس \(u\) از یکی از دو سر قطر \(AB\) (که این موضوع را قبلا نیز ثابت کرده بودیم).

دلیل این موضوع این است که اولا طبق لم 2.7.1 این خروج از مرکز \(u\) حداقل \(h(u)+H\) است. از طرف دیگر از راس \(u\) حداکثر \(h(u)\) یال می توان بالا رفت و حداکثر \(H\) یال می توان پایین رفت (زیرا طبق 2.7.2 ارتفاع درخت \(H\) است). در نتیجه خروج از مرکز حداکثر \(h(u) + H\) است که در نهایت ثابت می کند \(\varepsilon{(u)} = h(u) + H\).

قضیه 2.7.3

به راس هایی که می توانند یکی از دو سر قطر باشند راس قطری می گوییم. به راس هایی که ارتفاع آن ها \(H\) است راس های کف می گوییم. در اینجا ثابت می کنیم که یک راس قطری است اگر و فقط اگر کف باشد!

اگر راسی مثل \(u\) قطری باشد یعنی \(\varepsilon{(u)} = 2 \times H\) است. از آنجایی که \(\varepsilon{(u)} = h(u) + H\) می توان نتیجه گرفت که \(h(u) = H\) است که یعنی این راس کف است.

اگر راسی مثل \(u\) کف باشد یعنی \(h(u) = H\) است. طبق \(\varepsilon{(u)} = h(u) + H\) نتیجه می گیریم که \(\varepsilon{(u)} = 2 \times H\) است که یعنی این راس قطری است.

یک الگوریتم ساده تر

طبق لم 2.7.1 یکی دور ترین راس از \(u\) یکی از راس های کف است. از آنجایی که طبق قضیه 2.7.3 هر راس کف یک راس قطری نیز هست می توانیم نتیجه بگیریم دورترین راس از \(u\) یک سر قطر است!

بنابراین اگر دورترین راس از \(u\) (که یک راس دلخواه است) را پیدا کنیم و آن را \(A\) بنامیم آنگاه \(A\) یک سر قطر است. پس دورترین راس از \(A\) را در نظر بگیرید و آن را \(B\) بنامید. مسیر \(AB\) قطر درخت است.

این قضایا به ما الگوریتم ساده تری برای پیدا کردن قطر درخت پیشنهاد می دهند که پیاده سازی آن را در زیر می بینید. تابع far در واقع دور ترین راس از راس شروع را بر می گرداند.

const int maxn = 1e5 + 10;

vector<int> g[maxn];
int h[maxn];

int far(int u, int par = 0){
   h[u] = h[par] + 1;
   int ans = u;
   for(int y : g[u]){
       if(y != par){
           int p = far(y, u);
           if(h[p] > h[ans])
               ans = u;
       }
   }
   return ans;
}

int main(){
    // input
    int A = far(1);
    int B = far(A);
    // AB ghotr ast!
}