تجزیه سبک سنگین(HLD)
============

تعریف
-----------

یک روش کلاسیک مشابه گونی برای جواب دادن پرسمان های مربوط به مسیر در درخت است. مساله اصلی HLD در درخت ریشه دار افراز راس های درخت به تعدادی مسیر(chain) رو به بالا است به طوری که از هر برگی به سمت ریشه حرکت کنیم راس های حداکثر  :math:`O(lg(n))` مسیر را ببینیم.

الگوریتم تجزیه
----------------------------

ابتدا درخت را از راس یک ریشه دار می کنیم و اندازه زیردرخت هر راس(:math:`sz[i]`) را در زمان خطی حساب میکنیم. حال از ریشه :math:`dfs` میزنیم و chain ها را طوری پیدا میکنیم که راس های هر :math:`chain` یک بازه متوالی از راس هایی که میبینیم بسازند. اگر راسی که در آن هستیم(v) فرزندی داشت که اندازه اش از :math:`sz[v]/2` بیشتر یا مساوی بود به آن راس رفته و chain راس v را از ان فرزند ادامه میدهیم.(اگر هم چنین راسی وجود نداشت chain راس v را همان جا پایان میدهیم.) سپس از بقیه فرزندان راس فعلی dfs زده و هر کدام از انها را شروع chain ی جدید قرار میدهیم. 


اثبات درستی
----------------------------

از راس دلخواهی شروع کرده و به سمت ریشه بالا میرویم. متغیر :math:`X` را هم سایز زیردرخت راس فعلی تعریف میکنیم. هر بار که به سمت ریشه بالا میرویم(از ‍‍‍‍‍v به u) و وارد مسیر جدیدی میشویم, :math:`X` حداقل دوبرابر میشود. وگرنه :math:`sz[v]*2>sz[u]` که این یعنی راس v در ادامه chain راس u است و هنگام بالا رفتن وارد زنجیر جدیدی نمیشدیم.
یک بهینه سازی در افراز وجود دارد که لزومن زمان اجرا را بهتر نمیکند ولی از روی اثبات به وضوح می توان نتیجه گرفت زمان اجرا را بدتر نمیکند. هنگام افراز در حالتی که راس v هیچ فرزندی با سایز حداقل نصف v ندارد و اینکه راس v برگ نیست(حداقل یک فرزند دارد) به جای اینکه از زنجیر این راس را تمام کنیم انرا از بزرگترین فرزندش ادامه دهیم.(یعنی فرض کنیم سایز بزرگترین فرزندش حداقل نصف :math:`sz[v]` است). 


پیاده سازی الگوریتم
---------------------------

.. code-block:: cpp

	const int MAXN = 100010;

	int n, m, k, u, v, x, y;
	int par[MAXN], sz[MAXN], h[MAXN], head[MAXN];
	int stt[MAXN], fnt[MAXN], timer = 1;

	int dfs1(int node){ // finding subtree sizes
		h[node] = h[par[node]] + 1;
		for(int v: G[node])
			if(v != par[node]){
				par[v] = node;
				sz[node] += dfs1(v);
			}
		return ++sz[node];
	}
	void dfs2(int node, int hd){
		head[node] = hd;
		stt[node] = timer++;
		int big = 0;
		for(int v: G[node]) if(v != par[node] && sz[big] < sz[v]) big = v;
		if(big) dfs2(big, hd);
		for(int v: G[node]) if(v != par[node] && v != big) dfs2(v, v);
		fnt[node] = timer;
	}

	int main(){
		cin >> n;
		for (int i = 1; i < n; i++){
			cin >> u >> v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		dfs1(1);
		dfs2(1, 1);
		return 0;
	}


در اینجا هر chain یک بازه از راس ها بر حسب starting time را تشکیل میدهد. پس میتوانیم برای مسایل مختلف داده ساختاری مانند segment tree روی این ترتیب بسازیم و پرسمان مسیر را به :math:`O(lg(n))` از ان داده ساختار تبدیل کرد.(در اکثر درخت ها این مقدار خیلی کمتر از :math:`lg(n)` است)
همچنین در این روش از پیاده سازی میتوانیم پرسمان های مربوط به زیردرخت را هم جواب دهیم!