想不通怎么在交互题里重剖，于是使用随机化。
我们随便定一个根，然后随便选一个节点。我们可以用两次对当前所有点询问距离的方式求到两点之间的链。这样我们就求出了一些边。
我们借用淀粉质点分治的思想，将链上的所有点作为根，这样我们就把树切割成了若干个子树。这时我们可以直接算出链上点到子树的距离。复杂度期望 \(\mathrm O(n \log n)\)。
在 luogu 三发过了，在 qoj 好像有点非，十几发最高才 96.8352 分。
long long get_distance(int X, int Y);
void find_roads(int N, int Q, int A[], int B[], int W[]);#include <bits/stdc++.h>
#define llong long long
#define N 1005
using namespace std;mt19937 rnd(random_device{}());
vector<int> que[1000006]; int s[1000006], he, ta;
llong dis[N][N];inline llong getdis(int u, int v){if(dis[u][v]) return dis[u][v];return dis[u][v] = dis[v][u] = get_distance(u, v);
}void find_roads(int n, int Q, int A[], int B[], int W[]){he = ta = 1; int cnt = 0;for(int i = 1; i <= n; ++i) que[1].push_back(i);for(int i = 2; i <= n; ++i)dis[1][i] = getdis(1, i);s[1] = 1;while(he <= ta){int now = he++;if(que[now].size() == 1) continue;int u = s[now];int v = que[now][rnd()%que[now].size()];while(v == u) v = que[now][rnd()%que[now].size()];vector<int> line;for(int k : que[now])if(k != v) dis[v][k] = getdis(v, k);assert(dis[u][v]==dis[v][u]);for(int k : que[now])if(dis[u][k]+dis[v][k] == dis[u][v]) line.push_back(k);sort(line.begin(), line.end(), [&](int a, int b){return dis[u][a]<dis[u][b];});for(int i = 1; i < line.size(); ++i)A[cnt] = line[i-1], B[cnt] = line[i], W[cnt] = dis[u][line[i]]-dis[u][line[i-1]], ++cnt;for(int k : que[now]){for(int i = 0; i < line.size(); ++i){if(dis[u][k]-dis[u][line[i]] == dis[v][k]-dis[v][line[i]]){que[ta+i+1].push_back(k);dis[line[i]][k] = dis[u][k]-dis[u][line[i]];break;}}}for(int i : line) s[++ta] = i;}return;
}
#undef N
其实这个方法还能凸，因为我们没有用度数不大于 \(3\) 的性质。
对于非链头链尾的节点，注意到其出度为 \(1\)，于是我们可以少判一个节点。