Heavy-Light Decomposition

HL.cpp

// HL-decomposition
struct hl {
	int n;
	vector<vi> to, d;
	vi vd, vk, pv, dep;
	vector<bit> t; // bit
	int root;
	hl() {}
	hl(int mx):n(mx),to(mx),vd(mx),vk(mx),dep(mx) {}
	void add(int a, int b) {
		to[a].pb(b);
		to[b].pb(a);
	}
	int dfs(int v, int de=0, int p=-1) {
		dep[v] = de;
		vector<P> rs;
		rep(i,sz(to[v])) {
			int u = to[v][i];
			if (u == p) continue;
			rs.pb(P(dfs(u,de+1,v),u));
		}
		if (sz(rs)) {
			sort(rng(rs));
			vd[v] = vd[rs[0].se]; pv[vd[v]] = p;
			d[vd[v]].pb(v); vk[v] = -sz(d[vd[v]]);
			return rs[0].fi - (sz(rs) != 1 && rs[0].fi == rs[1].fi);
		} else {
			vd[v] = sz(d); vk[v] = -1; d.pb(vi(1,v)); pv.pb(p);
			return 1;
		}
	}
	void init(int v=0) {
		dfs(root = v);
		rep(i,sz(d)) reverse(rng(d[i]));
		rep(i,sz(vk)) vk[i] += sz(d[vd[i]]);
		rep(i,sz(d)) t.pb(bit(sz(d[i])+1)); // bit
	}
	int lca(int a, int b) {
		int p = vd[a]; vi ap(1,p);
		while (pv[p] != -1) ap.pb(p = vd[pv[p]]);
		reverse(rng(ap)); ap.pb(-2);
		p = vd[b]; vi bp(1,p);
		while (pv[p] != -1) bp.pb(p = vd[pv[p]]);
		reverse(rng(bp)); bp.pb(-3);
		int pi = 1; while (ap[pi] == bp[pi]) ++pi;
		p = ap[pi-1];
		int ai = vd[a]==p?vk[a]:vk[pv[ap[pi]]];
		int bi = vd[b]==p?vk[b]:vk[pv[bp[pi]]];
		return d[p][min(ai,bi)];
	}
	int sum(int p, int v) { // bit
		int res = 0;
		while (1) {
			int nd = vd[v], nk = vk[v];
			res += t[nd].sum(nk);
			if (nd == vd[p]) return res - t[nd].sum(vk[p]);
			v = pv[nd];
		}
	}
};
//