HDU5495

【中文题意】

【分析】因为无论怎么交换，a[i]和b[i]都是捆绑在一起的，所以每个a[i]和b[i]连边，则根据置换肯定有若干个环，而不难发现，每个换必然有L-1长度的LCS，这样统计出所有环即可。说来惭愧，本弱从来没做过置换的题目，所以比赛时就傻了。

【AC CODE】265ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXIN = 10000, MAXN = 1e5+10;
char buf[MAXIN], *ps = buf, *pe = buf+1;
inline void rnext(){
	if(++ps == pe) pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);
}
template <class T>
inline bool in(T &ans)
{
	ans = 0;
	T f = 1;
	if(ps == pe) return false;
	do{ rnext(); if('-' == *ps) f = -1;} while(!isdigit(*ps) && ps != pe);
	if(ps == pe) return false;
	do{ ans = (ans<<1)+(ans<<3)+*ps-48;rnext();}while(isdigit(*ps) && ps != pe);
	ans *= f;
	return true;
}
int a[MAXN],g[MAXN];
bool vis[MAXN];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	in(t);
	while(t--)
	{
		int n;
		in(n);
		repe(i,1,n) in(a[i]);
		repe(i,1,n)
		{
			int b;
			in(b);
			g[a[i]] = b;
		}
		clc(vis,0);
		int ans = n;
		repe(i,1,n)
		{
			if(vis[i]) continue;
			if(g[i] != i) ans--;
			int x = i;
			while(!vis[x])
			{
				vis[x] = true;
				x = g[x];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}