自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

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

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

以下是正文

前言

赛时只打出了特殊性质，还是太菜了 /kk。

解法

以下描述中，“原始状态”指的是未进行任何合并操作的树，“目标状态”指的是“进行完所有合并操作后的树”，$K_1(a)$ 表示节点 $a$ 在“原始状态”中的子节点集合，$K_2(a)$ 表示节点 $a$ 在“目标状态”中的子节点集合，$w_a$ 表示在目标状态中不存在的节点在操作过程中和它进行合并的节点。

令 $c_{a,b}$ 为“节点 $a$ 是否可以合并进节点 $b$”。显然的，若 $c_{a,b}$ 为真，那么 $a$ 和 $b$ 必须满足以下几个条件：

• 目标状态包含节点 $b$；

• $a\le b$，等号能取到当且仅当目标状态包含节点 $a$；

• $\forall i\in K_1(a)$，$\exists j\in K_2(b)$ 使得 $c_{i,j}$ 为真。

计算出 $c_{a,b}$ 不是难事，可以根据定义，从树的叶子节点开始按照深度递减一直算到根节点即可。

最后构造方案时，从根节点开始按照深度递增一直算到叶子节点，枚举每一个深度指定的节点 $a$，令其在原状态中的父亲为 $f$，那么只要找到一个最大的节点 $b$ 满足 $b$ 在目标状态中的父亲与 $w_f$ 相等（这样可以保证 $a,b$ 现在有同一个父亲）且 $c_{a,b}$ 为真，若最终 $a\ne b$ 就合并 $a,b$。

放代码：

/*
ID: CrowMatrix
TASK: Tree Merging
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int p1[1001],p2[1001],d[1001],w[1001];
bool e[1001],c[1001][1001];
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,r; cin>>n;
    for(int i=1;i<=n;i++)p1[i]=p2[i]=e[i]=w[i]=d[i]=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)c[i][j]=false;
    for(int i=1;i<n;i++){
      int v,p; cin>>v>>p; p1[v]=p;
    } // 原状态
    for(int i=1;i<=n;i++)if(!p1[i])r=i;
    int m; cin>>m; e[r]=true;
    for(int i=1;i<m;i++){
      int v,p; cin>>v>>p; p2[v]=p,e[v]=true;
    } // 目标状态
    for(int i=n;i;i--)
      for(int j=1;j<=n;j++)
        if(j!=r)d[j]=d[p1[j]]+1; // 计算节点深度
    for(int i=n;i;i--)
      for(int j=1;j<=n;j++)
        if(d[j]==i)
          if(e[j])c[j][j]=true;
          else for(int k=j;k<=n;k++)
            if(e[k])for(int l=c[j][k]=1;l<=n;l++)
              if(p1[l]==j){
                bool f=false;
                for(int p=1;p<=n;p++)
                  f|=p2[p]==k&&c[l][p];
                c[j][k]&=f; // 逐一检查各项条件是否满足
              }
    cout<<n-m<<endl; w[r]=r;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(d[j]==i){
          for(int k=1;k<=n;k++)
            if(p2[k]==w[p1[j]]&&c[j][k])w[j]=k; // 找合并的目标
          if(j!=w[j])cout<<j<<' '<<w[j]<<endl;
        }
  }
  return 0;
}