گونی¶

کاربرد¶

در مسائل زیادی می توان از گونی استفاده کرد که تعدادی در تمرین های این فصل آمده اند. اما برای این که بیشتر این مساله و اهمیت آن برای شما روشن شود، یک مثال با هم حل خواهیم کرد. در این مساله یک درخت ریشه دار داریم که هر راس آن یک رنگی دارد. به ازای هر زیر درخت می خواهیم تعداد رنگ های متفاوت آن را به دست بیاوریم و خروجی دهیم. فرض کنید که راه حل مساله گونی را بلدید و به کمک آن سعی کنید که مساله را حل کنید.

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

حال از الگوریتم گونی (که هم اکنون جزییات پیاده سازی آن را نمی دانیم) استفاده می کنیم. همه زیر درخت ها را یک بار در این داده ساختار می آوریم و پاسخشان را یادداشت می کنیم. سپس جواب ها را چاپ می کنیم.

الگوریتم¶

ایده گونی مشابه ایده جدا سازی سبک سنگین است که در فصل پایین ترین جد مشترک با آن آشنا شدیم. (برای یادآوری، می توانید به بخش 10.2 نگاهی بیاندازید) هدف ما این است که روی هر راس، به اندازه ضریبی از تعداد یال های سبکش در مسیر به ریشه عملیات انجام دهیم. یعنی تعداد حذف کردن و اضافه کردن های راس \(v\) به گونی در کل عملیات، از \(O(light_v)\) باشد. و از قسمت 10.2 به خاطر می آوریم که \(light_v \le lg(n)\) و بنابراین اگر موفق به این کار شویم، جمع عملیات ها روی تمام رئوس از \(O(nlg(n))\) خواهد بود.

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

در هنگام اجرای این تابع، همه فرزندان راس سنگین تنها به اندازه ای که تابع بازگشتی نیاز داشت از گونی اضافه و حذف شده اند و فرزندان راس های سبک، به جز آن، یک بار توسط تابع اصلی حذف و یک بار نیز اضافه شده اند. خود راس ورودی نیز در آخر یک بار اضافه شد. می توان دید که تعداد اضافه شدن و حذف شدن های هر راس مثل \(v\) دقیقا برابر \(2light_v+1\) خواهد شد. هم چنین می توان دریافت که زمان اجرای برنامه، ضریبی از تعداد عملیات های روی گونی است و هر دو طبق چیزی که در بالا مطرح شد از \(O(nlg(n))\) می باشند.

پیاده سازی¶

const int M = 1e5 + 5;
vector<int> g[M];
int sz[M]; // andaaze zirderakht har ras, baraaye tashkhis yaal haaye sabok va sangin

void add_to_gooni(int v) {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}
void remove_from_gooni(int v) {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}
void compute_answer() {
  // piade sazi motenaseb ba masale raa injaa gharaar dahid
}

void add_subtree(int v, int p){
    add_to_gooni(v);
    for(int u: g[v])
        if(u != p)
            add_subtree(u, v);
}
void remove_subtree(int v, int p){
    remove_from_gooni(v);
    for(int u: g[v])
        if(u != p)
            add_subtree(u, v);
}

void dfs(int v, int p){
    int mx = -1, bigChild = -1;
    for(int u : g[v]) {
      if(u != p && sz[u] > mx) {
        mx = sz[u];
        bigChild = u;
      }
    }
    for(int u : g[v]) {
      if(u != p && u != bigChild) {
        dfs(u, v); // javaabe farzand haye sabok ra mohaasebe mikonim
        remove_subtree(v, p); // sepas aan haa raa paak mikonim
      }
    }
    if(bigChild != -1)
        dfs(bigChild, v);  // farzande sangin raa paak nemikonim
    for(auto u : g[v]) {
      if(u != p && u != bigChild)
        add_subtree(u, v); // farzand haye sabok ra mojadadan bar migardaanim
    }
    compute_answer(); // hame zirderakht v dar gooni ast, javabash ra hesab mikonim
}

توجه کنید که در این پیاده سازی، باید گراف را ورودی بگیرید و مقادیر آرایه sz را با یک دی اف اس دیگر پر کنید که در این جا به آن اشاره نکردیم.