File size: 2,152 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 | #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);
for (int i = 1; i <= n; ++i) cin >> p[i];
vector<vector<pair<int,int>>> g(n + 1);
for (int i = 1; i <= n - 1; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back({v, i});
g[v].push_back({u, i});
}
vector<int> deg(n + 1);
vector<char> alive(n + 1, 1);
for (int i = 1; i <= n; ++i) deg[i] = (int)g[i].size();
int aliveCount = n;
vector<int> ops;
while (aliveCount > 0) {
vector<int> leaves;
leaves.reserve(aliveCount);
for (int i = 1; i <= n; ++i) {
if (alive[i] && deg[i] <= 1) leaves.push_back(i);
}
// Swap step: push tokens from leaves inward
for (int u : leaves) {
if (!alive[u]) continue;
if (deg[u] == 0) continue; // isolated node
if (p[u] == u) continue; // already correct
int v = -1, eid = -1;
for (auto &pr : g[u]) {
int w = pr.first, id = pr.second;
if (alive[w]) { v = w; eid = id; break; }
}
if (v == -1) continue; // no alive neighbor
swap(p[u], p[v]);
ops.push_back(eid);
}
// Removal step: remove leaves that are correct now
for (int u : leaves) {
if (!alive[u]) continue;
if (p[u] == u) {
alive[u] = 0;
--aliveCount;
for (auto &pr : g[u]) {
int w = pr.first;
if (alive[w]) --deg[w];
}
deg[u] = 0;
}
}
}
cout << ops.size() << '\n';
for (int e : ops) {
cout << 1 << ' ' << e << '\n';
}
}
return 0;
} |