题解：P12104 [NERC2024] Managing Cluster

· · 题解

考虑答案的上界就是树的最大匹配数，然后我们有合理的构造方式。

先说明树的最大匹配方式：dfs 一下，对于当前 u 去 dfs v，然后 v 回来时如果 u,v 都没配对那就给他俩配了，记录匹配的边。这实际上是一个贪心的过程。

然后我们考虑对颜色相同的点连颜色边，考虑匹配边和颜色边构成的一个东西。

然后会发现一个点的度数只有 1,2 两种情况，然后你会发现这个图是由一群链、环组成的，对于链的话直接首尾也连接一下即可，因为题目不关心最大匹配数只关心如何交换。

然后只考虑环如何交换即可。

首先一开始长这样：

然后我们开始第一次交换：

黑色表示你还能动，红色表示你不能动了。

方框表示匹配边，黑边表示颜色边。

然后是第二次交换：

然后是第三次交换：

发现第三次交换后的局面和第一次交换后的局面一样，说明第二次、第三次交换是一个周期，我们双指针模拟一下即可。

复杂度 O(Tn)。

int T = 1 ;
const int N = 1e5 + 2 ;
int n,a[N << 1] ;
vector<int> t[N << 1] ;
vector<pair<int,int>> me,ans ;
bool vis[N << 1] ;
int cbro[N << 1],tbro[N << 1],pos[N][2] ;
inline void match (fi u,fi fa) {
    for (re int v : t[u]) {
        if (v == fa) continue ;
        match(v,u) ;
        if (!vis[v] && !vis[u]) vis[u] = vis[v] = 1,me.emplace_back(u,v) ;
    }
}
inline void calc (vector<pair<int,int>> ce) {
    re int k = ce.size(),l = 1,r = k - 1 ;
    if (k <= 1) return ;
    ans.emplace_back(ce[0].first,ce[1].first) ;
    swap(ce[0].first,ce[1].first) ;
    while (l < r) {
        ans.emplace_back(ce[l].second,ce[r].second),swap(ce[l].second,ce[r].second) ;
        ++l ;
        if (l == r) break ;
        ans.emplace_back(ce[l].first,ce[r].first),swap(ce[l].first,ce[r].first) ;
        --r ;
        if (l == r) break ;
    }
}
inline void solve () {
    read(n) ;
    for (re int i = 1 ; i <= n << 1 ; ++i) read(a[i]) ;
    for (re int i = 2 ; i <= n << 1 ; ++i) {
        re int u,v ;
        read(u,v) ;
        t[u].push_back(v),t[v].push_back(u) ;
    }
    match(1,0) ;
    for (re int i = 1 ; i <= n << 1 ; ++i) {
        if (!pos[a[i]][0]) pos[a[i]][0] = i ;
        else {
            pos[a[i]][1] = i ;
            cbro[pos[a[i]][0]] = pos[a[i]][1] ;
            cbro[pos[a[i]][1]] = pos[a[i]][0] ;
        }
    }
    for (re auto &e : me) tbro[e.first] = e.second,tbro[e.second] = e.first ;
    fill(vis + 1,vis + 1 + (n << 1),0) ;
    for (re int i = 1 ; i <= (n << 1) ; ++i) {
        if (!tbro[i] && !vis[i]) {
            re vector<pair<int,int>> ce ;
            re int u = i,v = cbro[u] ;
            vis[u] = vis[v] = 1 ;
            while (tbro[v]) {
                u = tbro[v],vis[u] = 1 ;
                ce.emplace_back(v,u) ;
                v = cbro[u],vis[v] = 1 ;
            }
            if (ce.size()) {
                ce.emplace_back(v,i) ;
                calc(ce) ;
            }
        }
    }
    for (re int i = 1 ; i <= n << 1 ; ++i) {
        if (!vis[i]) {
            re vector<pair<int,int>> ce ;
            re int u = i,v = tbro[u] ;
            while (!vis[v]) {
                vis[u] = vis[v] = 1 ;
                ce.emplace_back(u,v) ;
                u = cbro[v],v = tbro[u] ;
            }
            if (ce.size()) calc(ce) ;
        }
    }
    write(ans.size(),endl) ;
    for (re auto &e : ans) write(e.first,' '),write(e.second,endl) ;
    ans.clear(),me.clear() ;
    for (re int i = 1 ; i <= n << 1 ; ++i) t[i].clear() ;
    fill(vis + 1,vis + 1 + (n << 1),0) ;
    fill(cbro + 1,cbro + 1 + (n << 1),0) ;
    fill(tbro + 1,tbro + 1 + (n << 1),0) ;
    for (re int i = 1 ; i <= n ; ++i) pos[i][0] = pos[i][1] = 0 ;
}
int main () {
    read(T) ;
    while (T--) solve() ;
    return 0 ;
}