درخت مجازی¶

اولین مسئله¶

فرض کنید زیرمجموعه ای از راس های درخت مثل \(B\) را سیاه کرده ایم. حالا می خواهیم تعدادی از راس هایی که سیاه نیستند را نیز سیاه کنیم به طوریکه کل راس های سیاه همبند باشند. همچنین می خواهیم تعداد راس های سیاه در نهایت کمینه شوند. این کمینه تعداد را بیابید.

واضح است که برای حل این سوال باید تمام راس هایی که بر روی مسیر حداقل دو راس سیاه هستند را سیاه کنیم. اما سوال مهم این است که چطور تعداد این راس ها را بیابیم به طوریکه پیچیدگی زمانی ما به \(|B|\) مربوط باشد و کاملا مستقل از \(n\) باشد. (یعنی اگر مجموعه‌ای که به ما دادند کوچک بود ما هم سریع جواب بدهیم و برعکس)

فرض کنید عدد جواب \(ans\) باشد. توجه کنید که خود \(ans\) ممکن است خیلی زیاد باشد و از مرتبه \(|B|\) نباشد. مثلا اگر درخت ما یک مسیر باشد و \(B\) مجموعه دو راس ابتدا و انتهای این مسیر باشد \(ans=n\) می شود. پس نمی توانیم از مرتبه زمانی \(ans\) هم کار کنیم.

حالا به این نکته جالب توجه کنید. حالت نهایی درخت را (که در آن راس های سیاه همبند هستند) را در نظر بگیرید و فرض کنید درجه سیاهی هر راس مثل \(u\) را تعداد راس های سیاه مجاور راس سیاه \(u\) تعریف می کنیم. همانطور که احتمالا از مثالی که برای مسیر زدیم متوجه شدید، ممکن است تعداد زیادی از راس هایی که مجبور به سیاه کردنشان هستیم درجه سیاهی ۲ داشته باشند!

یک معادل سازی روی مسئله انجام می دهیم تا کارمان راحت تر شود. درخت را از یکی از راس های \(B\) آویزان کنید. حالا به ازای هر راس \(u\) درون \(B\) تمام راس های از \(u\) تا ریشه باید سیاه شوند و همچنین این سیاه بودن کافی نیز هست (یعنی ساختار به دست آمده شرط همبند بودن را دارد).

در اینجا هست که مسئله ما کمی شبیه مسئله درخت مجازی می شود.فرض کنید آنقدر به مجموعه \(B\) راس اضافه کردیم که نسبت به \(lca\) بسته شد. یعنی تا زمانی که دو راس \(u, v\) درون \(B\) بودند که \(lca(u, v)\) درون \(B\) نبود ما باید \(lca(u, v)\) را سیاه کنیم و به \(B\) اضافه کنیم.

حالا به ازای هر راس غیر از ریشه مثل \(u\) پایین ترین جد سیاهش را پدر مجازی این راس بنامید که آن را با \(p_u\) نشان می دهیم. توجه کنید که حالا راس های بین \(u, p_u\) همان راس هایی بودند که گفتیم درجه سیاهی آنها ۲ می شود و ممکن است تعداد آنها زیاد باشد. حالا اگر به ازای تمام \(u, p_u\) هااین راس ها را بشماریم (که تعداد آن ها \(h_u - h_{p_u} - 1\) است) و این مقدار را با تعداد راس های سیاه فعلی جمع کنیم جواب مسئله به دست خواهد آمد.

در این قسمت به چند نکته کلیدی اشاره نکردیم. از جمله اینکه:

• چطور می توانیم راس هایی را پیدا کنیم که اگر به مجموعه \(B\) اضافه شوند درخت مجازی می سازند؟
• چرا تعداد حداکثر تعداد راس های درخت مجازی تنها به \(B\) مربوط است و ربطی به \(n\) ندارد؟

در ادامه به این سوال ها جواب می دهیم. همچنین لازم به ذکر است که سوالی که در این قسمت مطرح کردیم بدون عوض کردن ریشه هم به همان راحتی قایل حل است. عوض کردن ریشه ای که انجام دادیم صرفا به دلیل راحت تر کردن توضیحات بود!

قطر یک زیرمجموعه¶

فرض کنید یک درخت \(T\) و یک مجموعه \(B\) به شما داده اند. حالا شما باید دو تا از راس های درون \(B\) را نام ببرید که فاصله آن دو از یکدیگر بیشینه است.

الگوریتم پیدا کردن قطر درخت با dfs را در فصل ۲ بررسی کردیم. در اینجا هم اگر راس های \(B\) همبند باشند می توانیم از همان الگوریتم dfs استفاده کنیم. اگر همبند نبود چطور؟ دغدغه فعلی ما مشابه مسئله قبلی است. یعنی می خواهیم به ازای هر دو راس \(u,v\) از \(B\) تمام راس های حاظر در مسیر \(uv\) را به \(B\) اضافه کنیم و سپس روی گراف حاصل الگوریتم dfs را اجرا کنیم.

اما در حقیقت این کار روش خوبی نیست چون همانطور که در مسئله قبل بیان کردیم ممکن است تعداد راس هایی که نیاز داریم به \(B\) خیلی زیاد باشد.

در اینجا هم مثل مسئله قبل از درخت مجازی استفاده می کنیم. یعنی مجموعه \(B\) را آنقدر بسط می دهیم تا به یک درخت مجازی برسیم. حالا بین در یک گراف جدید بین هر راس و پدر مجازی خودش یالی با وزن \(h_u - h_{p_u}\) می کشیم. حالا درخت جدیدی که داریم همان درخت مجازی ما است! با پیدا کردن قطر در این درخت، بیشینه فاصله بین راس های \(B\) اولیه را پیدا می کنیم.

مقدمه¶

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

در این قسمت فرض می کنیم که مجموعه راس های \(B\) به ما داده شده است و ما می خواهیم تعدادی راس به آن اضافه کنیم تا \(B\) یک درخت مجازی شود. در اینجا این کار را بسط دادن می نامیم.

اولین تلاش¶

در گام اول می توانیم به ازای هر دو راس درون مجموعه \(B\) مثل \(a, b\) ، \(lca(a, b)\) را محاسبه کرده و آن را مجموعه \(C\) بنامیم.

حالا ادعا می کنیم \(D = B \cup C\) یک درخت مجازی است. برای اثبات توجه کنید که هر راس عضو \(D\) درون زیردرختش یک عضو از \(B\) موجود است. (چرا؟) حالا فرض کنید که دو راس \(a, b \in D\) باشند که \(lca\) آن دو درون \(D\) نباشد. راس های عضو \(B\) که درون زیردرخت \(a, b\) بودند را به ترتیب \(a\prime, a\prime\) بنامید. اگر \(lca(a, b)\) در \(D\) نیامده باشد آنگاه \(lca(a\prime, b\prime)\) همان \(lca(a, b)\) خواهد بود که در \(C\) است که با حرف اولیه ما تناقض دارد.

پس تنها کافیست به ازای هر دو راس درون \(B\) این محاسبات را انجام دهیم (و نیازی نیست که \(lca\) راس هایی که جدید اضافه می شوند را با بقیه بررسی کنیم)

یک الگوریتم بهتر¶

روشی که قبل از این گفتیم پیچیدگی زمانی بالایی داشت. اگر محسبات مربوط به \(lca\) را \(O(lg(n))\) در نظر بگیریم آنگاه روش بالا از \(O(|B|^2)\) خواهد بود.

حالا تلاش می کنیم که یک روش بهتر پیدا کنیم. یک راس به نام \(u\) را در نظر بگیرید که در \(B\) نیست اما باید در درخت مجازی باشد. یعنی دو راس \(u\) دو بچه \(a, b\) دارد که درون زبردرخت هر یک از \(a, b\) یک یا چند راس از \(B\) وجود دارد (که \(lca\) آن ها \(u\) خواهد شد)

حالا توجه کنید که از \(lca\) گرفتن هر کدام از راس های درون زیردرخت \(a\) با هر کدام از راس های درون زیردرخت \(b\) راس \(u\) به دست خواهد آمد. مشکل الگوریتم قبلی این بود که در این شرایط \(u\) را تعداد زیادی بار حساب می کرد که به این نیازی نداشتیم. یعنی به ازای هر زوج مرتب از راس های زیردرخت \(a, b\) یک بار راس \(u\) را حساب می کرد که دقیقا همین موضوع پیچیدگی زمانی راه قبل را زیاد می کرد.

نکته جالب این است که اگر بتوانیم برای راس های درخت \(T\) ترتیب اولیه ای قائل شویم که در این ترتیب زیردرخت هر راس به یک بازه تبدیل شود آنگاه می توانیم از روش زیراستفاده کنیم و ادعا کنیم به درستی عمل می کند.

• راس های \(B\) را بر حسب این ترتیب گفته شده مرتب کنید.
• حالا به ازای هر دو راس متوالی در لیست مرتب شده ای که به دست آوردیم \(lca\) این دو راس را به مجموعه \(C\) اضافه کنید.
• اجتماع دو مجموعه \(B, C\) درخت مجازی ما را تشکیل می دهند.

چرا این الگوریتم درست کار می کند؟ گفتیم راس \(u\) دو بچه دارد که در زیردرخت هر کدام راسی از \(B\) وجود دارد. در لیستی مرتب شده ای که الگوریتم را روی آن انجام دادیم یک بازه مربوط به زیر درخت \(u\) وجود دارد. در راس های مربوط به این بازه قطعا دو راس وجود داند که مربوط به زیردرخت بچه های متفاوتی از \(u\) هستند (چرا؟) بنابراین هنگامی که \(lca\) حساب می کنیم راس \(u\) به مجموعه \(C\) اضافه می شود! همانطور که می خواستیم.

ترتیب بهینه؟¶

در الگوریتم بالا به طور جادویی از یک ترتیب استفاده کردیم که ویژگی جالبی داشت. اما چنین ترتیبی ارائه ندادیم.

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

این دقیقا کاری است که در dfs آن را starting-time یا finishing-time می نامیم و آن را در فصل ۲ بررسی کردیم.

پیاده سازی¶

const int maxn = 1e5 + 10, max_log = 20;

int start_time[maxn], sparse_table[maxn][max_log], h[maxn];
vector<int> g[maxn];
int Counter = 0;

void dfs(int v, int par = 0){
  h[v] = h[par] + 1;
  sparse_table[v][0] = par;
  for(int i = 1; i < max_log; i++){
      sparse_table[v][i] = sparse_table[sparse_table[v][i-1]][i-1];
  }
  start_time[v] = Counter;
  Counter = Counter + 1;
  for(int u : g[v]){
      if(par != u){
          dfs(u, v);
      }
  }
}

int lca(int a, int b){
  if(h[a] < h[b])
      swap(a, b);
  for(int i = max_log-1; i >= 0; i--){
      if(h[sparse_table[a][i]] >= h[b])
          a = sparse_table[a][i];
  }
  if(a == b)
      return a;
  for(int i = max_log-1; i >= 0; i--){
      if(sparse_table[a][i] != sparse_table[b][i])
          a = sparse_table[a][i], b = sparse_table[b][i];
  }
  return sparse_table[a][0];
}

vector<int> build_virtual_tree(vector<int> vec){
  sort(vec.begin(), vec.end(), [](int a, int b){ return start_time[a] < start_time[b]; }); // sort on starting time
  for(int i = vec.size()-1; i > 0; i--){
      vec.push_back(lca(vec[i], vec[i-1]));
  }
  sort(vec.begin(), vec.end(), [](int a, int b){ return start_time[a] < start_time[b]; });
  vec.resize(unique(vec.begin(), vec.end())-vec.begin());
  return vec;
}

همچنین توجه کنید که اگر راس \(u\) درون درخت مجازی باشد و راس قبل از آن در ترتیب starting-time راس \(v\) باشد در اینصورت پدر مجازی راس \(u\) برابر با \(lca(u, v)\) می باشد. (چرا؟)

برای محاسبه \(lca\) در کد بالا از روشی با پیچیدگی زمانی \(O(lg(n))\) استفاده شد و در نهایت پیدا کردن بسط درخت مجازی مجموعه \(B\) با زمان \(O(|B| \times lg(n))\) انجام شد.