اُپدیا

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

در درختی با 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);
}