=====مقدمه===== تجزیه مرکزی درخت‌ها روشی برای پیاده‌سازی راه‌حل‌های تقسیم و حل بر درخت‌ها است. در این روش، با حذف مرکز یک درخت، آن را به درخت‌های کوچک‌تری تقسیم می‌کنیم. =====قضیه===== در درختی با N راس، راسی وجود دارد که با حذف آن گراف به درخت‌های به اندازه کمتر از $N/2$ تقسیم می‌شود. این راس را مرکز درخت می‌نامیم. ====اثبات==== ابتدا راسی دلخواه مانند v را انتخاب می‌کنیم. اگر آن راس خصوصیات مرکز درخت را نداشت، دقیقا یکی زیر‌درخت‌هایی که به آن متصل است اندازه‌ای بیشتر از $N/2$ دارد. حال راس u که راس مجاور v در آن زیر‌درخت است را انتخاب می‌کنیم و همان کار قبلی را با u می‌کنیم. این کار را ادامه می‌دهیم تا مرکز درخت را بیابیم. ما هیچ‌گاه به سراغ راس‌های قبلی نمی‌رویم، چرا که آن‌ها هم‌واره در زیر‌درخت‌هایی با کمتر از $N/2$ راس هستند. از آن‌جا که تعداد راس‌ها محدود است و هر کدام از آن‌ها را حداکثر یک بار انتخاب می‌کنیم، این الگوریتم پایان‌پذیر است و در نتیجه مرکز درخت وجود دارد. =====یافتن مرکز درخت===== الگوریتم گفته شده‌در اثبات قضیه وجود مرکز درخت را اعمال می‌کنیم. ابتدا اندازه تمام زیر‌درخت‌ها را یافته، و سپس همواره وارد زیردرخت با سایز بزرگ‌تر از $n/2$ می‌شویم تا زمانی که دیگر چنین زیردرختی وجود نداشته باشد. int n, size[Maxn]; bool mark[Maxn]; vector < int > adj[Maxn]; int size_finder(int v) { mark[v] = true; size[v] = 1; for(int u: adj[v]) if(!mark[u]) size[v] += size_finder(u); } int centroid(int n, int v){ mark[v] = true; for(int u: adj[v]) if(!mark[u] and size[u] > n/2) return centroid(n, u); return v; } int find_centroid(int V) { int v = 1 size_finder(v); memset(mark, 0, sizeof mark); return centroid(V, v); }