File size: 2,456 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n;
if (!(cin >> n)) return 0;
vector<vector<long long>> d(n + 1, vector<long long>(n + 1, 0));
for (int i = 1; i <= n; ++i) d[i][i] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
long long x;
cin >> x;
d[i][j] = d[j][i] = x;
}
}
if (n == 1) {
cout << "!\n";
continue;
}
vector<long long> dr(n + 1, 0);
for (int i = 1; i <= n; ++i) dr[i] = d[1][i];
vector<pair<long long,int>> order;
order.reserve(n);
for (int i = 1; i <= n; ++i) order.push_back({dr[i], i});
sort(order.begin(), order.end());
vector<int> processed;
processed.reserve(n);
processed.push_back(1);
vector<tuple<int,int,long long>> edges;
edges.reserve(n - 1);
for (auto &p : order) {
int v = p.second;
if (v == 1) continue;
long long D = -1;
int z = -1;
for (int w : processed) {
long long l = (dr[w] + dr[v] - d[w][v]) / 2;
if (l > D) {
D = l;
z = (dr[w] == l ? w : -1);
} else if (l == D) {
if (z == -1 && dr[w] == l) z = w;
}
}
if (z == -1) {
// Fallback: choose any with max l, then find ancestor by scanning processed
// but ideally shouldn't happen for valid tree metrics
for (int w : processed) {
long long l = (dr[w] + dr[v] - d[w][v]) / 2;
if (l == D) { z = w; break; }
}
}
long long wgt = dr[v] - D;
if (z == -1) z = 1; // safeguard
if (wgt < 0) wgt = 0; // safeguard
edges.emplace_back(z, v, wgt);
processed.push_back(v);
}
cout << "!";
for (auto &e : edges) {
int u, v;
long long w;
tie(u, v, w) = e;
cout << " " << u << " " << v << " " << w;
}
cout << "\n";
}
return 0;
} |