File size: 3,311 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 114 115 | #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>>> adj(n + 1);
vector<int> eu(n), ev(n); // 1..n-1
for (int i = 1; i <= n - 1; ++i) {
int u, v;
cin >> u >> v;
eu[i] = u;
ev[i] = v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
// Root the tree at 1
vector<int> parent(n + 1), parentEdge(n + 1), depth(n + 1);
stack<int> st;
parent[1] = 0;
parentEdge[1] = 0;
depth[1] = 0;
st.push(1);
while (!st.empty()) {
int u = st.top();
st.pop();
for (auto &pr : adj[u]) {
int v = pr.first, eidx = pr.second;
if (v == parent[u]) continue;
parent[v] = u;
parentEdge[v] = eidx;
depth[v] = depth[u] + 1;
st.push(v);
}
}
vector<int> ops;
ops.reserve(2LL * n * n);
auto getPathVertices = [&](int a, int b) {
vector<int> up, down;
int u = a, v = b;
while (u != v) {
if (depth[u] >= depth[v]) {
up.push_back(u);
u = parent[u];
} else {
down.push_back(v);
v = parent[v];
}
}
up.push_back(u); // LCA
reverse(down.begin(), down.end());
up.insert(up.end(), down.begin(), down.end());
return up;
};
auto addTransposition = [&](int a, int b) {
if (a == b) return;
auto path = getPathVertices(a, b);
int L = (int)path.size() - 1;
if (L <= 0) return;
vector<int> edges;
edges.reserve(L);
for (int i = 0; i < L; ++i) {
int x = path[i], y = path[i + 1];
int eidx;
if (parent[x] == y) eidx = parentEdge[x];
else eidx = parentEdge[y];
edges.push_back(eidx);
}
for (int e : edges) ops.push_back(e);
int sz = (int)edges.size();
for (int i = sz - 2; i >= 0; --i) {
ops.push_back(edges[i]);
}
};
vector<int> seen(n + 1, 0);
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
int cur = i;
vector<int> cyc;
while (!seen[cur]) {
seen[cur] = 1;
cyc.push_back(cur);
cur = p[cur];
}
if (cyc.size() <= 1) continue;
int c1 = cyc[0];
for (size_t j = 1; j < cyc.size(); ++j) {
int a = c1, b = cyc[j];
addTransposition(a, b);
}
}
}
cout << ops.size() << '\n';
for (int e : ops) {
cout << 1 << ' ' << e << '\n';
}
}
return 0;
} |