binary lifting.sublime-snippet

<snippet>
	<content><![CDATA[
const int LIFT_SIZE = 20;
class binaryLifting
{
public:
	class node
	{
	public:
		int par, depth;
		int bl[LIFT_SIZE];
		// xorBasis xb[LIFT_SIZE];
		node() {

		};
	};
	vector<vector<int>>adj;
	vector<node>tree;
	vector<int>A;
	void d_dfs(int cur, int par, int d)
	{
		tree[cur].depth = d;
		tree[cur].par = par;
		for (auto it : adj[cur])
		{
			if (it != par)
				d_dfs(it, cur, d + 1);
		}
		return;
	}
	void binary_lift(int curr, int par)
	{
		tree[curr].bl[0] = par;

		for (int i = 1; i < LIFT_SIZE; i++)
		{
			if (tree[curr].bl[i - 1] != -1)
			{
				tree[curr].bl[i] = tree[tree[curr].bl[i - 1]].bl[i - 1];
			}
			else
				tree[curr].bl[i] = -1;
		}

		for (auto it : adj[curr])
		{
			if (it != par)
				binary_lift(it, curr);
		}
		return;
	}
	int get_kth(int curr, int k)
	{
		for (int i = 0; i < LIFT_SIZE; i++)
		{
			if (curr == -1)
				return curr;
			if (k & (1 << i))
				curr = tree[curr].bl[i];
		}
		return curr;
	}
	int LCA(int a, int b)
	{
		int dis = abs(tree[a].depth - tree[b].depth);
		if (tree[a].depth < tree[b].depth)
		{
			b = get_kth(b, dis);
		}
		else if (tree[a].depth > tree[b].depth)
		{
			a = get_kth(a, dis);
		}
		if (a == b)
			return a;

		for (int i = LIFT_SIZE - 1; i >= 0; i--)
		{

			if (tree[a].bl[i] != tree[b].bl[i])
			{

				a = tree[a].bl[i];
				b = tree[b].bl[i];
			}
		}
		return tree[a].bl[0];
	};
	int distance(int a, int b)
	{
		int dis = abs(tree[a].depth - tree[b].depth);
		if (tree[a].depth < tree[b].depth)
		{
			b = get_kth(b, dis);
		}
		else if (tree[a].depth > tree[b].depth)
		{
			a = get_kth(a, dis);
		}
		if (a == b)
			return dis;
		for (int i = LIFT_SIZE; i >= 0; i--)
		{

			if (tree[a].bl[i] != tree[b].bl[i])
			{
				dis += (1LL << (i + 1));
				a = tree[a].bl[i];
				b = tree[b].bl[i];
			}
		}
		return dis + 2;
	}

	binaryLifting(vector<vector<int>>&adj, vector<int>&A)
	{
		this->adj = adj;
		this->A = A;
		int N = adj.size();
		tree.resize(N);
		d_dfs(0, -1, 0);
		binary_lift(0, -1);

	}
	binaryLifting()
	{

	}
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>binary lifting</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>