| #include <iostream> |
| #include <vector> |
| #include <algorithm> |
| #include <map> |
| using namespace std; |
|
|
| const int MAXN = 1005; |
| int n; |
| int p[MAXN]; |
| vector<pair<int,int>> adj[MAXN]; |
| int par[MAXN]; |
| int tin[MAXN], tout[MAXN], timer_val; |
| pair<int,int> edges[MAXN]; |
|
|
| void dfs_pre(int v, int pa) { |
| par[v] = pa; |
| tin[v] = ++timer_val; |
| for (auto& e : adj[v]) { |
| if (e.first != pa) dfs_pre(e.first, v); |
| } |
| tout[v] = ++timer_val; |
| } |
|
|
| bool in_subtree(int u, int v) { |
| return tin[u] <= tin[v] && tout[v] <= tout[u]; |
| } |
|
|
| |
| int dp_val[MAXN][2]; |
| int dp_child[MAXN]; |
| int w_edge[MAXN]; |
|
|
| void dp_dfs(int u, int pa) { |
| int sum = 0; |
| for (auto& e : adj[u]) { |
| int v = e.first; |
| if (v == pa) continue; |
| dp_dfs(v, u); |
| sum += max(dp_val[v][0], dp_val[v][1]); |
| } |
| dp_val[u][0] = sum; |
| dp_val[u][1] = -1000000; |
| dp_child[u] = -1; |
| for (auto& e : adj[u]) { |
| int v = e.first; |
| int eid = e.second; |
| if (v == pa) continue; |
| if (w_edge[eid] <= 0) continue; |
| int val = sum - max(dp_val[v][0], dp_val[v][1]) + dp_val[v][0] + w_edge[eid]; |
| if (val > dp_val[u][1]) { |
| dp_val[u][1] = val; |
| dp_child[u] = v; |
| } |
| } |
| } |
|
|
| void dp_reconstruct(int u, int pa, bool matched, vector<int>& result) { |
| if (matched) { |
| for (auto& e : adj[u]) { |
| if (e.first != pa) dp_reconstruct(e.first, u, false, result); |
| } |
| } else { |
| if (dp_val[u][1] > dp_val[u][0] && dp_child[u] != -1) { |
| int v = dp_child[u]; |
| int eid = -1; |
| for (auto& e : adj[u]) { |
| if (e.first == v) { eid = e.second; break; } |
| } |
| result.push_back(eid); |
| dp_reconstruct(v, u, true, result); |
| for (auto& e : adj[u]) { |
| if (e.first != pa && e.first != v) dp_reconstruct(e.first, u, false, result); |
| } |
| } else { |
| for (auto& e : adj[u]) { |
| if (e.first != pa) dp_reconstruct(e.first, u, false, result); |
| } |
| } |
| } |
| } |
|
|
| void solve() { |
| cin >> n; |
| for (int i = 1; i <= n; i++) { |
| cin >> p[i]; |
| adj[i].clear(); |
| } |
| for (int i = 1; i < n; i++) { |
| int u, v; |
| cin >> u >> v; |
| adj[u].push_back({v, i}); |
| adj[v].push_back({u, i}); |
| edges[i] = {u, v}; |
| } |
| timer_val = 0; |
| dfs_pre(1, 0); |
|
|
| vector<vector<int>> operations; |
| int max_iter = 3 * n; |
|
|
| while (max_iter-- > 0) { |
| bool sorted = true; |
| for (int i = 1; i <= n; i++) { |
| if (p[i] != i) { sorted = false; break; } |
| } |
| if (sorted) break; |
|
|
| |
| for (int i = 1; i < n; i++) { |
| int u = edges[i].first; |
| int v = edges[i].second; |
| int u_p, v_c; |
| if (par[v] == u) { u_p = u; v_c = v; } |
| else { u_p = v; v_c = u; } |
|
|
| int weight = 0; |
| if (p[u_p] != u_p) { |
| weight += in_subtree(v_c, p[u_p]) ? 1 : -1; |
| } |
| if (p[v_c] != v_c) { |
| weight += !in_subtree(v_c, p[v_c]) ? 1 : -1; |
| } |
| w_edge[i] = weight; |
| } |
|
|
| |
| for (int i = 1; i < n; i++) { |
| if (w_edge[i] < 0) w_edge[i] = 0; |
| } |
|
|
| dp_dfs(1, 0); |
| vector<int> matching; |
| dp_reconstruct(1, 0, false, matching); |
|
|
| if (matching.empty()) { |
| |
| for (int i = 1; i <= n; i++) { |
| if (p[i] != i) { |
| int target = p[i]; |
| if (in_subtree(i, target)) { |
| for (auto& e : adj[i]) { |
| if (e.first == par[i]) continue; |
| if (in_subtree(e.first, target)) { |
| matching.push_back(e.second); |
| break; |
| } |
| } |
| } else { |
| for (auto& e : adj[i]) { |
| if (e.first == par[i]) { |
| matching.push_back(e.second); |
| break; |
| } |
| } |
| } |
| break; |
| } |
| } |
| if (matching.empty()) break; |
| } |
|
|
| operations.push_back(matching); |
| for (int eid : matching) { |
| swap(p[edges[eid].first], p[edges[eid].second]); |
| } |
| } |
|
|
| cout << operations.size() << "\n"; |
| for (auto& op : operations) { |
| cout << op.size(); |
| for (int eid : op) cout << " " << eid; |
| cout << "\n"; |
| } |
| } |
|
|
| int main() { |
| ios_base::sync_with_stdio(false); |
| cin.tie(NULL); |
| int t; |
| cin >> t; |
| while (t--) solve(); |
| return 0; |
| } |
|
|
