File size: 3,641 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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 | #include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) cin >> p[i];
vector<pair<int, int>> edges(n - 1);
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
edges[i] = {u, v};
adj[u].push_back(v);
adj[v].push_back(u);
}
// Precompute all-pairs distances in the tree
vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1));
for (int s = 1; s <= n; s++) {
queue<int> q;
dist[s][s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[s][v] == -1) {
dist[s][v] = dist[s][u] + 1;
q.push(v);
}
}
}
}
vector<int> cur = p; // current numbers on vertices
vector<vector<int>> operations; // list of operations
while (true) {
// Check if we have reached the identity permutation
bool sorted = true;
for (int i = 1; i <= n; i++) {
if (cur[i] != i) {
sorted = false;
break;
}
}
if (sorted) break;
// Compute delta (gain) for each edge
vector<pair<int, int>> deltas; // (delta, edge_index)
for (int idx = 0; idx < n - 1; idx++) {
int u = edges[idx].first, v = edges[idx].second;
int x = cur[u], y = cur[v];
int delta = (dist[u][y] + dist[v][x]) - (dist[u][x] + dist[v][y]);
deltas.emplace_back(delta, idx);
}
sort(deltas.begin(), deltas.end()); // sort by delta ascending
// Collect edges with non‑positive delta
vector<pair<int, int>> neg_edges;
for (auto& pr : deltas) {
if (pr.first <= 0) neg_edges.push_back(pr);
}
vector<bool> used(n + 1, false);
vector<int> selected;
// Greedily pick a matching from non‑positive edges
for (auto& pr : neg_edges) {
int idx = pr.second;
int u = edges[idx].first, v = edges[idx].second;
if (!used[u] && !used[v]) {
selected.push_back(idx);
used[u] = used[v] = true;
}
}
// If no edge was selected, take the one with the smallest delta
if (selected.empty()) {
int idx = deltas[0].second;
selected.push_back(idx);
}
// Apply the swaps of this operation
for (int idx : selected) {
int u = edges[idx].first, v = edges[idx].second;
swap(cur[u], cur[v]);
}
// Store the operation (edge indices are 1‑based in the output)
vector<int> op;
for (int idx : selected) op.push_back(idx + 1);
operations.push_back(op);
}
// Output the solution
cout << operations.size() << "\n";
for (auto& op : operations) {
cout << op.size();
for (int e : op) cout << " " << e;
cout << "\n";
}
}
return 0;
} |