自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:12:46，当前版本为作者最后更新于2025-04-09 14:22:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

使用贪心或者 DP 求解一个树上的最大匹配 $M=\{(u_1,v_1),(u_2,v_2),\ldots,(u_k,v_k)\}$，则答案不会超过 $k$。

大胆猜测答案一定可以取到 $k$，以下是构造方法：

对于上面的最大匹配 $M$，构造一个有 $n$ 个结点的无向图 $G$，连边 $a_{u_i}\leftrightarrow a_{v_i}(1\le i\le k)$。由于原树上每个结点在最大匹配中最多出现一次，而 $a_i$ 在 $a$ 中恰好出现两次，所以该图中结点度数不超过 $2$。

我们先引入一个叫做“缩二度点”的操作：假设在 $G$ 中，对于结点 $x$ 有边 $x\leftrightarrow y$ 和 $x\leftrightarrow z$，那么意味着在最大匹配中有两条边满足 $a_{u_i}=x,a_{v_i}=y$ 和 $a_{u_j}=x,a_{v_j}=z$；此时交换 $v_i,u_j$，即可以将匹配中的边调整为 $a_{u_i}=a_{v_i}=x$ 和 $a_{u_j}=y,a_{v_j}=z$——对应到 $G$ 中，相当于删除了边 $x\leftrightarrow y$ 和 $x\leftrightarrow z$（$x$ 直接满足条件，可以不管了），加入了一条新边 $y\leftrightarrow z$，十分类似广义串并联图中的“缩二度点”操作。

考察 $G$ 的性质，由于结点度数不超过 $2$，所以 $G$ 中的每个连通块要么是一个环，要么是一条链：使用上面的“缩二度点”操作，一个环可以被缩成一个单点（即环上所有结点全部调整完毕），而一条链最后必然被缩成 $x\leftrightarrow y$ 的形态：思考造成这种现象的本质，由于这两个结点度数都为 $1$，那么满足 $a_i=x$ 的某个 $i$ 必然没有被选入最大匹配中！此时只需要将 $y$ 在匹配中对应的结点和那个没被选入的 $i$ 交换即可。

根据不同实现，时间复杂度为 $O(n\log n)$ 或 $O(n)$。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
vector<pii> matching(vector<vector<int> > g){
  vector<bool> b(g.size());
  vector<pii> r;
  function<void(int,int)> dfs=[&](int u,int f){
    for(int i:g[u])
      if(i!=f)dfs(i,u);
    if(u&&!b[u]&&!b[f])
      r.emplace_back(u,f),b[u]=b[f]=true;
  };
  return dfs(0,0),r;
} // 求最大匹配
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> a(n<<1);
    for(auto &i:a)cin>>i,i--;
    vector<vector<int> > g(n<<1),c(n);
    for(int i=1;i<n<<1;i++){
      int u,v; cin>>u>>v;
      g[--u].emplace_back(--v);
      g[v].emplace_back(u);
    }
    auto m=matching(g);
    vector<set<int> > s(n);
    vector<int> p(n<<1,-1);
    for(int i=0;i<n<<1;i++)
      s[a[i]].emplace(i);
    for(auto [x,y]:m){
      p[x]=y,p[y]=x;
      c[a[x]].emplace_back(a[y]);
      c[a[y]].emplace_back(a[x]);
    } // 基于最大匹配建图
    vector<bool> b(n),b2(n<<1);
    vector<pii> r;
    auto solve=[&](int x){
      vector<int> v;
      function<void(int)> dfs=[&](int u){
        b[u]=true,v.emplace_back(u);
        for(int i:c[u])
          if(!b[i])dfs(i);
      };
      dfs(x); // 找环 / 链
      auto op=[&](int u,int v){
        int w=0,x=-1,y=-1;
        for(int i:s[u])w^=i;
        for(int i:s[u])
          for(int j:s[v])
            if(p[i]==j&&!b2[w^i])x=w^i,y=j;
        r.emplace_back(x,y),b2[x]=b2[y]=true;
        s[v].erase(y),s[v].emplace(x);
      }; // “缩二度点”操作
      for(int l=v.size()-1>>1,r=l+1,f=1;0<=l&&r<v.size();(f=!f)?r++:l--)
        f?op(v[l],v[r]):op(v[r],v[l]); // 在链 / 环上缩点
    };
    for(int i=0;i<n;i++)
      if(c[i].size()==1&&!b[i])solve(i); // 链
    for(int i=0;i<n;i++)
      if(c[i].size()==2&&!b[i])solve(i); // 环
    cout<<r.size()<<'\n';
    for(auto [x,y]:r)
      cout<<x+1<<' '<<y+1<<'\n';
  }
  return 0;
}