docker_space/frontier_cs_9/solution.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;

const int MAXN = 1005;
int n;
int p_orig[MAXN], 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);
            }
        }
    }
}

vector<vector<int>> run_greedy(mt19937& rng, int noise_level) {
    for (int i = 1; i <= n; i++) p[i] = p_orig[i];

    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 * 100;
            if (weight > 0 && noise_level > 0) {
                w_edge[i] += rng() % noise_level;
            }
            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]);
        }
    }
    return operations;
}

int T_cases;
int case_idx;
clock_t global_start;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p_orig[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);

    mt19937 rng(42 + n + case_idx * 1000);

    // Run without noise first
    auto best_ops = run_greedy(rng, 0);

    // Allocate remaining time proportional to n^2 (estimated work)
    double elapsed = (double)(clock() - global_start) / CLOCKS_PER_SEC;
    double remaining_time = 0.9 - elapsed;

    // For small n, very few trials needed; allocate most time to large n
    double case_deadline;
    if (n <= 20) {
        // Small cases: just run a few hundred trials, takes no time
        case_deadline = elapsed + 0.01;
    } else {
        int remaining_cases = T_cases - case_idx;
        double time_per_case = remaining_time / remaining_cases;
        case_deadline = elapsed + time_per_case;
    }

    // Run randomized trials until deadline
    int trial_count = 0;
    while (trial_count < 5000) {
        double now = (double)(clock() - global_start) / CLOCKS_PER_SEC;
        if (now > case_deadline) break;
        trial_count++;
        int noise = 10 + rng() % 90;
        auto ops = run_greedy(rng, noise);
        if (ops.size() < best_ops.size()) {
            best_ops = ops;
        }
    }

    cout << best_ops.size() << "\n";
    for (auto& op : best_ops) {
        cout << op.size();
        for (int eid : op) cout << " " << eid;
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    global_start = clock();
    cin >> T_cases;
    for (case_idx = 0; case_idx < T_cases; case_idx++) {
        solve();
    }
    return 0;
}