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

استفاده از 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);
       }
   }
}

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

قطر درخت یک خاصیتی دارد که به ما کمک می کند تا آن را ساده تر پیدا کنیم. آن خاصیت این است: دور ترین راس نسبت به هر راس، سر یکی از خطر های درخت است.

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

از این خاصیت می توان استفاده کرد و قطر درخت را پیدا کرد. تابعی می نویسیم که یک راس ورودی بگیرد و به کمک الگوریتم دی اف اس یکی از دور ترین رئوس نسبت به این راس را برگرداند. این تابع را از یک راس دلخواه اجرا می کنیم و نتیجه را \(u\) می نامیم. یکبار هم این تابع را از \(u\) اجرا می کنیم و نتیجه را \(v\) می نامیم. چون از قضیه بالا می دانستیم که راس \(u\) سر یکی از قطر های درخت است، پس مسیر \(uv\) یکی از قطر های درخت است.