指针写法

思路一样，提供一种指针建树的写法。

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
	// unordered_map<int,int,custom_hash>ma;
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
const int N=2000;
struct TreeNode
{
	TreeNode * left;
	TreeNode * right;
	int val;
};
int n,ans,a[N],b[N];
bool f;
TreeNode * solve(int l,int r,int L,int R)
{
	if(l>r || L>R)return NULL;

	TreeNode * rt=new TreeNode;
	rt->val=a[l];
	rt->left=NULL;
	rt->right=NULL;

	unordered_map<int,int,custom_hash>ma;
	for(int i=l;i<=r;i++)
	{
		ma[a[i]]=1;
	}
	for(int i=L;i<=R;i++)
	{
		if(ma[b[i]]!=1)
		{
			f=true;
		}
	}

	for(int i=L;i<=R;i++)
	{
		if(b[i]==a[l])
		{
			rt->left=solve(l+1,l+i-L,L,i-1);
			rt->right=solve(l+i-L+1,r,i+1,R);
			break;
		}
	}
	return rt;
}
void dfs(TreeNode * root,int d)
{
	if(root->left==NULL && root->right==NULL)
	{
		ans+=d;
		return ;
	}
	if(root->left!=NULL)dfs(root->left,d+1);
	if(root->right!=NULL)dfs(root->right,d+1);
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	f=false;
	ans=0;
	TreeNode * root=solve(1,n,1,n);
	dfs(root,0);
	if(f)cout<<"-1\n";
	else cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}