Heavy-Light Decomposition

devil_coder · December 15, 2013, 5:20pm

Can someone provide a good tutorial(well explained) or provide some link on how to exactly implement H-L Decomposition. I have searched a lot and been through almost all suggested websites. The main problem is in the segment tree part. I have seen some implementations but cant understand really why all that is being done.

A walk, through code would be really helpful in understand the essence.

Thank You

infinitum · December 15, 2013, 5:27pm

These are good for getting a basic idea of HLD

http://wcipeg.com/wiki/Heavy-light_decomposition

devil_coder · December 15, 2013, 5:35pm

I have gone through these links but still cant implement. The segment tree part to answer queries is actually the real problem.

siam_cr7 · June 15, 2017, 8:46am

This is a good tutorial on HLD by Anudeep.

Some basic problem to solve using HLD:
Problem1 , Problem2

adarsh_007 · June 15, 2017, 9:03am

https://apps.topcoder.com/forums/?module=Thread&threadID=796128&start=0&mc=8

Codeforces:

http://codeforces.com/blog/entry/12239

Praveen dhinwa:

adarsh_007 · June 15, 2017, 9:07am

Code:

github.com

PetarV-/Algorithms/blob/master/Graph Algorithms/Heavy-Light Decomposition.cpp

/*
 Petar 'PetarV' Velickovic
 Algorithm: Heavy-Light Decomposition
*/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <complex>
#define MAX_N 1000001

This file has been truncated. show original