#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<pair<int, int>, ll> mp;
ll ask(int i, int j)
{
if (i == j)
{
return 0;
}
if (i > j)
{
swap(i, j);
}
if (!mp.count({i, j}))
{
mp[{i, j}] = get_distance(i + 1, j + 1);
}
return mp[{i, j}];
}
void find_roads(int n, int q, int e_a[], int e_b[], int e_w[])
{
int root = 0;
vector<ll> dist0(n, 0);
vector<int> ord;
for (int i = 0; i < n; i++)
{
if (root == i)
{
dist0[i] = 0;
continue;
}
dist0[i] = ask(root, i);
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&] (int i, int j) {return dist0[i] < dist0[j];});
vector<int> deja = {0};
vector<vector<int>> g(n);
vector<int> sub(n), big(n), u(n), par(n);
int top = 0;
auto add_edge = [&] (int a, int b)
{
e_a[top] = a + 1;
e_b[top] = b + 1;
e_w[top] = dist0[b] - dist0[a];
g[a].push_back(b);
top++;
};
function<void(int)> dfs = [&] (int a)
{
sub[a] = 1;
if (g[a].empty())
{
u[a] = a;
return;
}
big[a] = g[a][0];
for (auto &b : g[a])
{
dfs(b);
par[b] = a;
sub[a] += sub[b];
if (sub[b] > sub[big[a]])
{
big[a] = b;
}
}
u[a] = u[big[a]];
};
function<void(int, int)> locate = [&] (int root, int new_vertex)
{
if (sub[root] == 1)
{
add_edge(root, new_vertex);
return;
}
int b = u[root];
ll dist_b_v = ask(b, new_vertex);
ll dist_b_r = dist0[b] - dist0[root];
ll dist_v_r = dist0[new_vertex] - dist0[root];
ll sum_dub = (dist_b_v + dist_b_r + dist_v_r);
ll sum = sum_dub / 2;
ll z = sum - dist_b_r;
ll x = sum - dist_b_v;
ll y = sum - dist_v_r;
int fix_inainte = -1;
if (y == 0)
{
add_edge(b, new_vertex);
return;
}
while (y > 0)
{
y -= (dist0[b] - dist0[par[b]]);
fix_inainte = b;
b = par[b];
}
int mid_point = b;
if (z == 0)
{
add_edge(mid_point, new_vertex);
return;
}
if ((int) g[mid_point].size() == 1)
{
add_edge(mid_point, new_vertex);
return;
}
vector<int> oth;
for (auto &vecin : g[mid_point])
{
if (vecin == fix_inainte)
{
continue;
}
oth.push_back(vecin);
}
if ((int) oth.size() == 1)
{
if (dist0[oth[0]] - dist0[mid_point] >= z)
{
add_edge(mid_point, new_vertex);
return;
}
if (ask(u[oth[0]], new_vertex) == z + dist0[u[oth[0]]] - dist0[mid_point])
{
add_edge(mid_point, new_vertex);
return;
}
locate(oth[0], new_vertex);
return;
}
if (ask(oth[0], new_vertex) < ask(oth[1], new_vertex))
{
locate(oth[0], new_vertex);
}
else
{
locate(oth[1], new_vertex);
}
};
for (auto &vertex : ord)
{
dfs(root);
locate(root, vertex);
}
}
