سنتروید¶

تعریف¶

در درخت به راسی که با حذف آن تعداد راس های بزرگترین مولفه حداکثر \(n/2\) باشد سنتروید می گوییم.

اثبات وجود و یافتن سنتروید¶

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

const int N = 100000 + 77;
int n , sz[N];
vector < int > adj[N];

void dfs(int v ,int prev = -1) {
   sz[v] = 1;
   for(int u : adj[v])
      if(u != prev){
         dfs(u , v);
         sz[v] += sz[u];
       }
}
int FindCentroid(int v , int prev = -1) {
   for(int u : adj[v])
      if(u != prev && sz[u] * 2 > n)
         return FindCentroid(u, v);
   return v;
}
int main() {
   scanf("%d" , & n);
   for(int v, u, i = 1; i < n; ++i){
      scanf("%d %d" ,& v ,& u);
      adj[v].push_back(u);
      adj[u].push_back(v);
    }
   dfs(1);
   printf("%d\n" , FindCentroid(1));
   return 0;
}

Centroid Decomposition¶

فرض کنید می خواهیم روی درخت الگوریتم تقسیم و حل را پیاده سازی کنیم سنتروید درخت کمک بسیاری به ما خواهد کرد چون می توانیم با حذف آن و حل زیر درخت های باقی مانده به پیچیدگی \(O(n log n)\) برسیم . اگر دقت کنید با این تکنیک روی هر راس حداکثر \(lg n\) بار پیمایش کرده ایم چون با هر بار پیمایش روی آن رای اندازه مولفه اش کمتر از نصف می شود پس در کل پیچیدگی زمانی اش \(O(n log n)\) خواهد شد پیاده سازی این روش به این صورت است که ابتدا centroid درست را پیدا می کنیم حال هر کدام از مولفه ها را جداگانه حل می کنیم که همانند روش تقسیم و حل است. پیاده سازی الگوریتم را در ادامه ببینید

const int N = 100000 + 77;
int n, sz[N];
bool M[N]; // che rass haee centroid shodeand ta be hal
vector < int > adj[N];

void dfs(int v, int prev = -1) {
   sz[v] = 1;
   for(int u : adj[v])
      if(u != prev && ! M[u]){
         dfs(u, v);
         sz[v] += sz[u];
       }
}

int FindCentroid(int v, int prev = -1) {
   for(int u : adj[v])
      if(u != prev && sz[u] * 2 > n)
         return FindCentroid(u, v);
   return v;
}
void Decompose(int v) {
   dfs(v);
   int c = FindCentroid(v);
   M[c] = 1;
   for(int u : adj[c])
      if(! M[u])
         Decompose(u);
}

int main() {
   scanf("%d", & n);
   for(int v, u, i = 1; i < n; ++i){
      scanf("%d %d" , & v , & u);
      adj[v].push_back(u);
      adj[u].push_back(v);
    }
   Decompose(1);
   return 0;
}

Centroid Tree¶

فرض کنید درختی جدید از درختی که داریم میسازیم الگوریتم Centroid Decomposition را در نظر بگیرید حال در هر مرحله که سنتروید یک زیر درخت را پیدا می کنیم پدر آن را در این درختی که می سازیم سنتروید مولفه قبلی که این راس را داشته می گذاریم به این درخت جدید Centroid Tree می گوییم

درخت اولیه

درخت سنتروید

در بسیاری از سوال ها Centroid Tree کمک بسیاری در محاسبات می کند