File size: 4,316 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 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | #include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Structure to represent an edge
struct Edge {
int u, v, id;
};
int n;
vector<int> p; // Permutation
vector<vector<int>> adj; // Adjacency list
vector<Edge> edges; // List of all edges
vector<int> tin, tout; // DFS entry and exit times for subtree checks
int timer;
// DFS to compute entry/exit times
void dfs_tin(int u, int parent) {
tin[u] = ++timer;
for (int idx : adj[u]) {
int v = (edges[idx].u == u) ? edges[idx].v : edges[idx].u;
if (v != parent) {
dfs_tin(v, u);
}
}
tout[u] = timer;
}
// Check if u is an ancestor of v
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
// Check if value val (currently at u_curr) wants to move towards neighbor v_next
bool wants_to_move(int u_curr, int v_next, int val) {
int target = val; // value x wants to go to node x
// If v_next is a child of u_curr
if (is_ancestor(u_curr, v_next)) {
// v_next is child. val wants to go to v_next if target is in v_next's subtree
return is_ancestor(v_next, target);
} else {
// v_next is parent. val wants to go to v_next if target is NOT in u_curr's subtree
return !is_ancestor(u_curr, target);
}
}
void solve() {
if (!(cin >> n)) return;
p.assign(n + 1, 0);
for (int i = 1; i <= n; ++i) cin >> p[i];
adj.assign(n + 1, vector<int>());
edges.clear();
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
edges.push_back({u, v, i + 1}); // Store 1-based index
adj[u].push_back(i);
adj[v].push_back(i);
}
tin.assign(n + 1, 0);
tout.assign(n + 1, 0);
timer = 0;
// Root the tree at 1 for parent/child relationships
dfs_tin(1, 0);
vector<vector<int>> ops;
while (true) {
bool sorted = true;
for(int i = 1; i <= n; ++i) {
if(p[i] != i) {
sorted = false;
break;
}
}
if (sorted) break;
vector<int> type1; // Indices of edges where both want to cross (Priority 1)
vector<int> type2; // Indices of edges where one wants to cross (Priority 2)
for (int i = 0; i < edges.size(); ++i) {
int u = edges[i].u;
int v = edges[i].v;
int pu = p[u];
int pv = p[v];
bool u_wants_v = wants_to_move(u, v, pu);
bool v_wants_u = wants_to_move(v, u, pv);
if (u_wants_v && v_wants_u) {
type1.push_back(i);
} else if (u_wants_v || v_wants_u) {
type2.push_back(i);
}
}
if (type1.empty() && type2.empty()) break; // Should not happen if not sorted
vector<bool> matched(n + 1, false);
vector<int> current_op_edges;
// Greedy matching for Type 1
for (int idx : type1) {
int u = edges[idx].u;
int v = edges[idx].v;
if (!matched[u] && !matched[v]) {
matched[u] = true;
matched[v] = true;
current_op_edges.push_back(edges[idx].id);
swap(p[u], p[v]);
}
}
// To avoid cycles with Type 2 swaps, vary the order (e.g., reverse every other round)
if (ops.size() % 2 != 0) {
reverse(type2.begin(), type2.end());
}
// Greedy matching for Type 2
for (int idx : type2) {
int u = edges[idx].u;
int v = edges[idx].v;
if (!matched[u] && !matched[v]) {
matched[u] = true;
matched[v] = true;
current_op_edges.push_back(edges[idx].id);
swap(p[u], p[v]);
}
}
if (current_op_edges.empty()) break;
ops.push_back(current_op_edges);
}
cout << ops.size() << "\n";
for (const auto& op : ops) {
cout << op.size();
for (int id : op) cout << " " << id;
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
if (cin >> t) {
while (t--) {
solve();
}
}
return 0;
} |