docker_space/frontier_cs_9/test_solution.cpp

#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]; // {neighbor, edge_id}
int par[MAXN]; // parent in rooted tree
int tin[MAXN], tout[MAXN], timer_val;
pair<int,int> edges[MAXN]; // edge i -> {u, v}

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) { // is v in subtree of u?
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

// Maximum weight matching on tree using DP
int dp_val[MAXN][2];
int dp_child[MAXN]; // which child v is matched to (for reconstruction)
int w_edge[MAXN]; // weight of edge i

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;

        // Compute edge weights
        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;
        }

        // Set negative weights to 0
        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()) {
            // Fallback: find unsorted element, move it one step toward target
            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;
}