[USACO23OPEN] Tree Merging G 题解

· · 题解

前言

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

解法

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

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

计算出 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;
}