Function path_intersection

Graph Theory/Path Intersection.cpp:68–79

returns the intersection of two paths (a,b) and (c,d) {0,0} for null path

// returns the intersection of two paths (a,b) and (c,d)
// {0,0} for null path
pair<int, int> path_intersection(int a, int b, int c, int d) {
  if (a == 0 || b == 0) return {0, 0};
  int u = lca(a, b), v = lca(c, d); // splits both paths in two chains from lca to one node
  pair<int, int> x, y;
  x = getCommonPath(u, a, v, c);
  y = getCommonPath(u, a, v, d);
  pair<int, int> a1 = path_union_light(x, y);
  x = getCommonPath(u, b, v, c);
  y = getCommonPath(u, b, v, d);
  pair<int, int> a2 = path_union_light(x, y);
  return path_union_light(a1, a2);
}
int32_t main() {
  int t, cs = 0; cin >> t;
  while (t--) {