graph.snippets

snippet read_tree
for (int id_edge = 0; id_edge < nb_node-1; ++id_edge) {
	int u, v;
	cin >> u >> v;
	--u; --v;
	adj[u].push_back(v);
	adj[v].push_back(u);
}

endsnippet

snippet read_graph
for (int id_edge = 0; id_edge < nb_edge; ++id_edge) {
	int u, v;
	cin >> u >> v;
	--u; --v;
	adj[u].push_back(v);
	adj[v].push_back(u);
}

endsnippet

snippet read_weighted
for (int id_edge = 0; id_edge < nb_edge; ++id_edge) {
	int u, v;
	ll w;
	cin >> u >> v >> w;
	--u; --v;
	adj[u].emplace_back(v, w);
	adj[v].emplace_back(u, w);
}

endsnippet

snippet dijkstra
vector<ll> dist(nb_node, 1e18);
priority_queue<pair<ll, int>> pq;
dist[$1] = 0;
pq.push({0LL, $1});
while (!pq.empty()) {
	ll ds = -pq.top().first;
	int node = pq.top().second;
	pq.pop();
	if (ds != dist[node]) continue;
	for (auto edge : adj[node]) {
		int neighbour = edge.fi;
		ll weight = edge.se;
		if (ds+weight < dist[neighbour]) {
			dist[neighbour] = ds+weight;
			pq.push({-dist[neighbour], neighbour});
		}
	}
}$0
endsnippet

snippet bfs
vector<int> dist(nb_node, 1e9);
queue<int> qq;
dist[$1] = 0;
qq.push($1);
while (!qq.empty()) {
	int node = qq.front();
	qq.pop();
	for (int neighbour : adj[node]) {
		if (dist[node]+1 < dist[neighbour]) {
			dist[neighbour] = dist[node]+1;
			qq.push(neighbour);
		}
	}
}$0
endsnippet

snippet small_to_large 
void ${1:dfs}(int node, int parent) {
	int heavy = -1;
	for (int child : adj[node]) if (child != parent) {
		$1(child, node);
		if (heavy == -1 || vsz(${2:set}[child]) > vsz($2[heavy]))
			heavy = child;
	}

	if (heavy != -1) {
		$2[node].swap($2[heavy]);
		for (int child : adj[node]) if (child != parent && child != heavy) {
			for (auto elem : $2[child]) {
				$2[node].insert(elem);
			}
		}
	}
}

$0
endsnippet

snippet LCA
struct LCA {
	using DT = long long;
	static const int UNDEF = -1;
	static const int height = $1; 
	static const int maxNode = 1 << (height - 1);
	static_assert(maxNode >= $2);

	int ancester[maxNode][height];
	DT infoPath[maxNode][height];
	int depth[maxNode];

	vector<pair<int, DT>> adj[maxNode];

	void addEdge(int u, int v, DT weight) {
		adj[u].push_back({v, weight});
		adj[v].push_back({u, weight});
	}

	void build(int node, int par = UNDEF, DT wp = 0) {
		depth[node] = (par == UNDEF ? 0 : depth[par] + 1);
		ancester[node][0] = par;
		infoPath[node][0] = wp;
		for (int level = 1; level < height; ++level) {
			int tmp = ancester[node][level-1];
			if (tmp == UNDEF) {
				ancester[node][level] = UNDEF;
			} else {
				ancester[node][level] = ancester[tmp][level-1];
				infoPath[node][level] = $3(infoPath[node][level-1], infoPath[tmp][level-1]);
			}
		}

		for (auto rawEnf : adj[node]) if (rawEnf.first != par) {
			build(rawEnf.first, node, rawEnf.second);
		}
	}

	pair<int, DT> lcaAndInfo(int u, int v) {
		if (depth[u] > depth[v]) {
			swap(u, v);
		}
		DT info = $4; // BE CAREFUL
		// v is deepest
		for (int level = height-1; level >= 0; --level) {
			int anc = ancester[v][level];
			if (anc != UNDEF && depth[anc] >= depth[u]) {
				info = $3(info, infoPath[v][level]);
				v = anc;
			}	
		}
		if (u == v) {
			return {u, info};
		}
		// u and v on the same depth
		for (int level = height-1; level >= 0; --level) {
			int a1 = ancester[u][level];
			int a2 = ancester[v][level];
			if (a1 != UNDEF && a2 != UNDEF && a1 != a2) {
				info = $3(info, infoPath[u][level]);
				info = $3(info, infoPath[v][level]);
				u = a1;
				v = a2;
			}
		}
		info = $3(info, infoPath[u][0]);
		info = $3(info, infoPath[v][0]);
		return { ancester[u][0], info };

	} 

	int getLca(int u, int v) {
		return lcaAndInfo(u,v).first;
	}
};
// DON'T FORGET TO BUILD

$0
endsnippet