File size: 3,545 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 | #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;
cin >> n;
vector<int> p(n + 1), pos(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> p[i];
pos[p[i]] = i;
}
vector<vector<pair<int,int>>> adj(n + 1);
vector<pair<int,int>> edges(n); // 1..n-1
for (int i = 1; i <= n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
edges[i] = {u, v};
}
vector<int> deg(n + 1, 0);
vector<char> active(n + 1, 1);
for (int i = 1; i <= n; ++i) deg[i] = (int)adj[i].size();
deque<int> leafq;
for (int i = 1; i <= n; ++i) if (deg[i] <= 1) leafq.push_back(i);
int activeCnt = n;
vector<int> swaps; swaps.reserve(n * n / 2 + 5);
vector<int> parent(n + 1), parentEdge(n + 1);
vector<char> vis(n + 1);
while (activeCnt > 1) {
int u = -1;
while (!leafq.empty()) {
int x = leafq.front(); leafq.pop_front();
if (active[x] && deg[x] <= 1) { u = x; break; }
}
if (u == -1) break; // should not happen
int start = pos[u]; // current position of token u
if (start != u) {
// BFS from start to u within active vertices
fill(vis.begin(), vis.end(), 0);
queue<int> q;
q.push(start);
vis[start] = 1;
parent[start] = -1;
parentEdge[start] = -1;
while (!q.empty() && !vis[u]) {
int x = q.front(); q.pop();
for (auto [y, eid] : adj[x]) {
if (!active[y] || vis[y]) continue;
vis[y] = 1;
parent[y] = x;
parentEdge[y] = eid;
if (y == u) break;
q.push(y);
}
}
// reconstruct path nodes from start to u
vector<int> nodes;
int cur = u;
nodes.push_back(cur);
while (cur != start) {
cur = parent[cur];
nodes.push_back(cur);
}
reverse(nodes.begin(), nodes.end());
// perform swaps along the path
for (size_t i = 0; i + 1 < nodes.size(); ++i) {
int a = nodes[i], b = nodes[i + 1];
int eid = parentEdge[b];
swaps.push_back(eid);
int ta = p[a], tb = p[b];
// swap tokens on vertices a and b
p[a] = tb; p[b] = ta;
pos[tb] = a; pos[ta] = b;
}
}
// remove leaf u from active tree
active[u] = 0;
--activeCnt;
int par = -1;
for (auto [v, eid] : adj[u]) {
if (active[v]) { par = v; break; }
}
if (par != -1) {
--deg[par];
if (deg[par] == 1) leafq.push_back(par);
}
deg[u] = 0;
}
cout << swaps.size() << '\n';
for (int eid : swaps) {
cout << 1 << ' ' << eid << '\n';
}
}
return 0;
} |