راه حل O(n+q*lg(n)) به کمک جداسازی سبک-سنگین

در این بخش برای مساله‌های گفته شده یک راه حل \(O(n+q*lg(n))\) را بیان می‌کنیم.

جداسازی سبک-سنگین

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

تعداد یال های سبک در مسیر به ریشه

تعداد یال‌های سبک در مسیر هر راس به ریشه، حداکثر \(O(lg(n))\) است. (چرا؟)

حل مساله جد در ارتفاع خاص

حداکثر یک فرزند یک راس می تواند سنگین باشد پس می توانیم در DFS اول به سراغ راس با یال سنگین برویم تا زمان ورود فرزند سنگین دقیقا یک واحد بیشتر از پدرش باشد. به این ترتیب اگر راس ها را بر اساس زمان ورود مرتب کنیم، هر کس که یال به پدرش سنگین است، دقیقا بعد پدرش قرار می‌گیرد.

این ترتیب را به دست بیاورید و هم‌چنین برای هر راس به دست بیاورید چند پدرش دقیقا به ترتیب پشت سرش قرار گرفته‌اند یا به عبارت دیگر به دست بیاورید که اولین یال سبک در مسیر این راس به ریشه متعلق به کدام راس است.

حال برای اینکه جد یک راس در ارتفاع خاصی را به دست بیاوریم، اگر تعداد پدر هایی که پشت این راس آمده اند از ارتفاع مطلوب بیشتر باشد، یا به عبارت دیگر همه یال ها به جد مطلوب، یال سنگین باشند. در این حالت می‌توانیم در زمان \(O(1)\) جد مطلوب را به دست بیاوریم. اما اگر یال سبکی این وسط بود باید به جدی که یال به پدرش سبک است برویم، سپس پدر آن را بدست آوریم و از آن پدر کار را ادامه دهیم. چون حداکثر \(O(lg(n))\) یال سبک در مسیر هر راس به ریشه وجود دارد، این کار در نهایت \(O(lg(n))\) به ازای هر پرسش طول می‌کشد و بنابراین پیچیدگی زمانی کل، \(O(n+q*lg(n))\) است.

#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+5;

int edge_counter = 1;

int st[M], stp[M], hld[M], par[M], h[M];
vector<int> g[M];
int time = 0;

int dfsz(int x, int p = 0) {
  int sz = 1, mxsz = -2;
  if (p == g[x][0]) swap(g[x][0], g[x][g[x].size()-1]);
  for (int i = 0; i < g[x].size(); i++) {
    if (g[x][i] == p) continue;
    int szy = dfsz(g[x][i], x);
    sz += szy;
    if (szy > mxsz) {
      mxsz = szy;
      swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
    }
  }
  return sz;
}

void dfst(int stpx, int p = 0) {
  int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
  stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
  for (int stpy: g[stpx]) {
    if (stpy == p) continue;
    dfst(stpy, stpx);
    par[st[stpy]] = x;
  }
}

int parat(int stpx, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
  int x = hld[st[stpx]];
  while (h[x] > hgoal) x = hld[par[x]];
  return stp[x+hgoal-h[x]];
}

int main(){
  // derakht ra voroodi begirid va yal ha ra dar g berizid
  dfsz(0);
  dfst(0);
  for (int x = 1; x < n; x++) {
    h[x] = h[par[x]] + 1;
    hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
  }
  // sepas porsesh ha ra ba parat pasokh dahid
}

حل مساله LCA

طبق چیزی که در قسمت قبل گفتیم با راه بالا می توان یک راه \(O(n+q*lg^2(n))\) برای مساله پایین ترین جد مشترک ارائه داد. اما به سادگی می‌توانیم راه حل را بهینه‌تر کنیم. پایین ترین جد مشترک را در نظر بگیرید. مسیر یکی از راس ها به این راس یالش حتما سبک است (هر دو یال نمی‌توانند سنگین باشند) بنابراین با الگوریتم زیر می توانیم پایین ترین جد مشترک را پیدا کنیم. بدست بیاورید که یال سبک کدام راس پایین‌تر است. آن راس را بدست آورید و جد هم ارتفاع متناظرش با راس دیگر را به دست آورید. سپس پدر هر دو راس را حساب کنید. اگر مساوی بودند که ما جد مشترک را پیدا کرده‌ایم و در غیر این صورت با دو راس جدیدی که پیدا کردیم کار را ادامه می‌دهیم. چون حداکثر دو برابر لاگ رئوس درخت یال سبک در مسیر وجود خواهد داشت این الگوریتم پیچیدگی زمانی \(O(n+q*lg(n))\) دارد.

#include<bits/stdc++.h>

using namespace std;

const int M = 1e5+5;

int edge_counter = 1;

int st[M], stp[M], hld[M], par[M], h[M];
vector<int> g[M];
int time = 0;

int dfsz(int x, int p = 0) {
  int sz = 1, mxsz = -2;
  if (p == g[x][0]) swap(g[x][0], g[x][g[x].size()-1]);
  for (int i = 0; i < g[x].size(); i++) {
    if (g[x][i] == p) continue;
    int szy = dfsz(g[x][i], x);
    sz += szy;
    if (szy > mxsz) {
      mxsz = szy;
      swap(g[x][0], g[x][i]); // enteghale yal sangin be g[x][0]
    }
  }
  return sz;
}

void dfst(int stpx, int p = 0) {
  int x = st[stpx] = time++; // shomare ras ha ra joori avaz mikonim ke yal haye sangin
  stp[x] = stpx; // motevali bashand. in jayghasht ra dar st[x] va barakse aan ra dar stp[x] mirizim
  for (int stpy: g[stpx]) {
    if (stpy == p) continue;
    dfst(stpy, stpx);
    par[st[stpy]] = x;
  }
}

int parat(int x, int hgoal) { // jadi az rase voroodi ke ertefae hadaf ra darad ra mikhahim
  int x = hld[x];
  while (h[x] > hgoal) x = hld[par[x]];
  return x+hgoal-h[x];
}

int lca(int stpx, int stpy) {
  int x = st[stpx], y = st[stpy];
  if (h[x]<h[y]) swap(x,y);
  x = parat(x, h[y]); // do ras ra ham ertefa mikonim ta kod sade tar shavad
  while (x != y) {
    x = hld[x]; y = hld[y];
    if (h[x]<h[y]) swap(x,y);
    y += h[x] - h[y];
    x = par[x]; y = par[y];
  }
  return stp[x];
}

int main(){
  // derakht ra voroodi begirid va yal ha ra dar g berizid
  dfsz(0);
  dfst(0);
  for (int x = 1; x < n; x++) {
    h[x] = h[par[x]] + 1;
    hld[x] = par[x] == x - 1 ? hld[x-1] : x; // hld[x] bala tarin jadi ast ke be aan yale sangin darim
  }
  // sepas porsesh ha ra ba parat pasokh dahid
}