我觉得理论上答案的最大值为 $n-1$，于是当无解时得出的最小步数设置为 $n$，就得到以下程序

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXT=20,MAXN=50;

struct UE
{
	int x,y;
	void Scan()
	{
		scanf("%d %d",&x,&y);
		if(x>y) swap(x,y);
	}
}Ae[MAXN+5],Be[MAXN+5];

bool cmp(UE a,UE b) {return (a.x==b.x ? a.y<b.y : a.x<b.x);}

int n,D[MAXN+5],ans;
vector<int> A[MAXN+5],B[MAXN+5],G[MAXN+5];
int Afa[MAXN+5],Bfa[MAXN+5],inD[MAXN+5];

bool Zero()
{
	sort(Ae+1,Ae+n,cmp),sort(Be+1,Be+n,cmp);
	for(int i=1;i<n;i++)
		if(Ae[i].x!=Be[i].x || Ae[i].y!=Be[i].y) return 0;
	return 1;
}

void GetFaA(int now,int fa)
{
	Afa[now]=fa;
	for(int i=0,rear;i<A[now].size();i++)
	{
		rear=A[now][i];
		if(rear==fa) continue;
		GetFaA(rear,now);
	}
}

void GetFaB(int now,int fa)
{
	Bfa[now]=fa;
	for(int i=0,rear;i<B[now].size();i++)
	{
		rear=B[now][i];
		if(rear==fa) continue;
		GetFaB(rear,now);
	}
}

bool NeedModify(int x) {return Afa[x]!=Bfa[x];}

int Q[MAXN+5],Head,Tail;
void Topo()
{
	Head=1,Tail=0;
	for(int i=1;i<=n;i++)
		if(!inD[i]) Q[++Tail]=i;
	for(int now,rear;Head<=Tail;)
	{
		now=Q[Head++];
		for(int i=0;i<G[now].size();i++)
			if(!--inD[rear=G[now][i]]) Q[++Tail]=rear;
	}
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) D[i]=0,B[i].clear();
		for(int i=1;i<n;i++) Ae[i].Scan(),++D[Ae[i].x],++D[Ae[i].y];
		for(int i=1;i<n;i++)
		{
			Be[i].Scan();
			B[Be[i].x].push_back(Be[i].y);
			B[Be[i].y].push_back(Be[i].x);
		}
		if(Zero()) {printf("0\n");continue;}
		ans=n;
		for(int i=1;i<=n;i++)
			if(D[i]<2)
				for(int j=1;j<=n;j++)
				{
					if(i==j) continue;
					for(int k=1;k<=n;k++) A[k].clear();
					A[i].push_back(j),A[j].push_back(i);
					for(int k=1;k<n;k++)
						if(Ae[k].x!=i && Ae[k].y!=i)
						{
							A[Ae[k].x].push_back(Ae[k].y);
							A[Ae[k].y].push_back(Ae[k].x);
						}
					for(int k=1;k<=n;k++) G[k].clear();
					GetFaA(i,0),GetFaB(i,0);
					int cnt=1;
					for(int k=1;k<=n;k++) inD[k]=0;
					for(int k=1;k<=n;k++)
					{
						if(k==i) continue;
						if(NeedModify(k))
						{
							++cnt;
							if(NeedModify(Afa[k])) G[k].push_back(Afa[k]),++inD[Afa[k]];
							if(NeedModify(Bfa[k])) G[Bfa[k]].push_back(k),++inD[k];
						}
						else if(NeedModify(Afa[k])) {cnt=n;break;}
					}
					Topo();
					for(int k=1;k<=n;k++)
						if(inD[k]) {cnt=n;break;}
					ans=min(ans,cnt);
				}
		if(ans==n) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

然后 WA 了，观察题解发现大家都把上限设置成 $n$，于是程序修改为

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXT=20,MAXN=50;

struct UE
{
	int x,y;
	void Scan()
	{
		scanf("%d %d",&x,&y);
		if(x>y) swap(x,y);
	}
}Ae[MAXN+5],Be[MAXN+5];

bool cmp(UE a,UE b) {return (a.x==b.x ? a.y<b.y : a.x<b.x);}

int n,D[MAXN+5],ans;
vector<int> A[MAXN+5],B[MAXN+5],G[MAXN+5];
int Afa[MAXN+5],Bfa[MAXN+5],inD[MAXN+5];

bool Zero()
{
	sort(Ae+1,Ae+n,cmp),sort(Be+1,Be+n,cmp);
	for(int i=1;i<n;i++)
		if(Ae[i].x!=Be[i].x || Ae[i].y!=Be[i].y) return 0;
	return 1;
}

void GetFaA(int now,int fa)
{
	Afa[now]=fa;
	for(int i=0,rear;i<A[now].size();i++)
	{
		rear=A[now][i];
		if(rear==fa) continue;
		GetFaA(rear,now);
	}
}

void GetFaB(int now,int fa)
{
	Bfa[now]=fa;
	for(int i=0,rear;i<B[now].size();i++)
	{
		rear=B[now][i];
		if(rear==fa) continue;
		GetFaB(rear,now);
	}
}

bool NeedModify(int x) {return Afa[x]!=Bfa[x];}

int Q[MAXN+5],Head,Tail;
void Topo()
{
	Head=1,Tail=0;
	for(int i=1;i<=n;i++)
		if(!inD[i]) Q[++Tail]=i;
	for(int now,rear;Head<=Tail;)
	{
		now=Q[Head++];
		for(int i=0;i<G[now].size();i++)
			if(!--inD[rear=G[now][i]]) Q[++Tail]=rear;
	}
}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++) D[i]=0,B[i].clear();
		for(int i=1;i<n;i++) Ae[i].Scan(),++D[Ae[i].x],++D[Ae[i].y];
		for(int i=1;i<n;i++)
		{
			Be[i].Scan();
			B[Be[i].x].push_back(Be[i].y);
			B[Be[i].y].push_back(Be[i].x);
		}
		if(Zero()) {printf("0\n");continue;}
		ans=n+1;
		for(int i=1;i<=n;i++)
			if(D[i]<2)
				for(int j=1;j<=n;j++)
				{
					if(i==j) continue;
					for(int k=1;k<=n;k++) A[k].clear();
					A[i].push_back(j),A[j].push_back(i);
					int cnt=1;
					for(int k=1;k<n;k++)
						if(Ae[k].x!=i && Ae[k].y!=i)
						{
							A[Ae[k].x].push_back(Ae[k].y);
							A[Ae[k].y].push_back(Ae[k].x);
						}
					for(int k=1;k<=n;k++) G[k].clear();
					GetFaA(i,0),GetFaB(i,0);
					for(int k=1;k<=n;k++) inD[k]=0;
					for(int k=1;k<=n;k++)
					{
						if(k==i) continue;
						if(NeedModify(k))
						{
							++cnt;
							if(NeedModify(Afa[k])) G[k].push_back(Afa[k]),++inD[Afa[k]];
							if(NeedModify(Bfa[k])) G[Bfa[k]].push_back(k),++inD[k];
						}
						else if(NeedModify(Afa[k])) {cnt=n+1;break;}
					}
					Topo();
					for(int k=1;k<=n;k++)
						if(inD[k]) {cnt=n+1;break;}
					ans=min(ans,cnt);
					if(cnt==4)
					{
						printf("find %d %d\n",i,j);
						for(int k=1;k<=n;k++)
						{
							printf("%d:",k);
							for(int l=0;l<G[k].size();l++) printf(" %d",G[k][l]);
							printf("\n");
						}
					}
				}
		if(ans>n) printf("-1\n");
		else printf("%d\n",ans);
	}
	return 0;
}

修改的地方在于输出时判断 $ans>n$，并且当发现无解时 $cnt=n$，然后就 AC 了。

这是否说明存在情况使得答案能达到 $n$ 呢！但是我怎么也构造不出来啊！有大佬能帮忙看看问题出哪了吗