看到除我以外的记录全是多少带个迭代器,指针变量什么的，深感心痛。

我这个大蒟蒻根本看不懂啊啊啊！

并且，如果此题数据再增强一点变为$1 \le n \le 10^6$的话，官方题解就挂了。

于是，今天，我就要写一篇无指针+O(n)代码，以让像我一样蒟蒻的人看懂代码！

这边建树流程和官方一样，不过我把判定也写在里边了。

至于求值……

当然是暴力查树啦

于是，代码也随之出现——

#include <bits/stdc++.h>
using namespace std;
struct node{
	int l=0,r=0;
}tree[1111];
int xi[1111],zh[1111],ma[1111];
bool f=0;
int jian(int xl,int xr,int zl,int zr){
	//cout<<"BBB "<<xl<<" "<<xr<<" "<<zl<<" "<<zr<<endl;
	if (xl>xr && zl>zr){
		return 0;
	}
	if (xl==xr){
		if (xi[xl]!=zh[zl]){//判断一号
			f=1;
			return 0;
		}
	}
	int rt=xi[xl];//取第一个
	int k=ma[rt];//找根
	//cout<<"K "<<k<<endl;
	if (k==-1 || k<zl || k>zr){//判断二号
		//cout<<"AAA "<<xl<<" "<<xr<<" "<<zl<<" "<<zr<<endl;
		f=1;
		return 0;
	}
	tree[rt].l=jian(xl+1,k-zl+xl,zl,k-1);
	if (f){//判断三号
		return 0;
	}
	tree[rt].r=jian(k-zl+xl+1,xr,k+1,zr);
	if (f){//判断四号
		return 0;
	}
	return rt;
}
int di(int p,int h){//p:节点编号，h:深度
	if (tree[p].l==0 && tree[p].r==0){
		return h;//叶子直接返回
	}
	int sum=0;
	if (tree[p].l!=0){
		sum+=di(tree[p].l,h+1);//不必多说
	}
	if (tree[p].r!=0){
		sum+=di(tree[p].r,h+1);//不必多说^2
	}
	return sum;
}
int main() {
    int t;
    cin>>t;
    while (t--){
    	f=0;
    	int n;
    	cin>>n;
    	for (int i=0;i<n;++i){
    		cin>>xi[i];
		}
		for (int i=0;i<=n;++i){
			ma[i]=-1;//初始
		}
		for (int i=0;i<n;++i){
    		cin>>zh[i];
    		ma[zh[i]]=i;//记录值对应的编号
		}
    	int rt=jian(0,n-1,0,n-1);//建树，同时求出根节点。
    	if (f){
    		cout<<-1<<endl;
    		continue;
		}
    	int ans=di(rt,0);
    	cout<<ans<<endl;
	}
    return 0;
}

时间复杂度：
建树最坏将每个点都遍历一次，为O(n)。
求值最坏也是将每个点都遍历一次，自然为O(n)。
最后，总复杂度便是O(n)

好像大家都省略了T……
如果看到了本文，请评论，谢谢。
总之，希望这篇题解会对你理解题目有些关注。给个赞吧
bye~