[BJOI 2015] 나무의 동 질감.

[제목]
전송 문
Description
나 무 는 흔히 볼 수 있 는 데이터 구조 이다.
우 리 는 n n 개의 점, n - 1 n - 1 개의 변 의 연결 무 방향 도 를 나무 라 고 부른다.
어떤 점 을 뿌리 로 하고 뿌리 부터 옮 겨 다 니 면 다른 점 은 모두 전구 가 있 고 이 나 무 는 뿌리 가 있 는 나무 가 된다.
두 나무 t 1 t1 t1 과 t 2 t2 t2 t2 에 대해 나무 t 1 t1 t1 의 모든 점 을 다시 표시 하여 나무 t 1 t1 t1 과 나무 t 2 t2 t2 t2 를 똑 같이 만 들 수 있다 면 이 두 나 무 는 같은 구조 입 니 다.같은 형 태 를 갖 고 있다 는 얘 기다.
지금, 당신 에 게 m m m 개 에 나무 가 있 습 니 다. 그것들 을 같은 구조 관계 에 따라 몇 개의 등가 류 로 나 누 어 주 십시오.
Input
첫 줄, 정수 m m.
다음 m m 줄 은 줄 마다 몇 개의 정 수 를 포함 하고 나 무 를 표시 합 니 다.첫 번 째 정수 n n n 은 점 수 를 나타 낸다.다음은 n n 개의 정수 로 번호 가 11 부터 n n 까지 의 각 점 의 아버지 결산 점 의 번 호 를 차례대로 나타 낸다.뿌리 노드 의 아버지 결점 번 호 는 000 이다.
Output
m m 줄 을 출력 하고 줄 마다 정 수 를 표시 하 며 모든 나무 와 같은 구조의 나무의 최소 번 호 를 표시 합 니 다.
Sample Input
4 4 0 1 1 2 4 2 0 2 3 4 0 1 1 1 4 0 1 2 3
Sample Output
1 1 3 1
HINT
[사례 해석] 번호 가 1, 2, 4, 1, 2, 4, 1, 2, 4 인 나 무 는 같은 구조 이다.번호 가 333 인 나 무 는 그 자체 와 만 같다.100% 100 \ \% 100% 의 데이터 중, 11 1 ≤ n, m n, m n, m ≤ 50 50.
[분석]
우선 괄호 순 서 를 말씀 해 주세요.
d f s dfs dfs 순 서 를 고려 하여 d f s dfs dfs 가 한 점 을 완성 할 때 우 리 는 똑 같이 그 를 서열 에 넣 었 다. 이렇게 얻 은 서열 을 괄호 서열 이 라 고 한다.한 그루 의 나무 에 대해 하위 노드 가 질서 가 있 으 면 이 나 무 는 괄호 서열 에 유일 하 게 대응 합 니 다.
그러면 이 문제 에 대해 서 는 사실 괄호 서열 만 찾 으 면 된다.
지금 또 두 가지 문제 가 있다.

두 그루 의 나무 에 대해 뿌리 가 다 르 면 구조 가 같 더 라 도 괄호 서열 이 다르다

두 그루 의 나무 에 대해 서 는 뿌리 가 같 지만 d f s dfs dfs 의 순서 가 다 르 면 괄호 서열 도 다르다

.
그래서 지금 문 제 는 뿌리 를 어떻게 찾 고 d f s dfs dfs 를 어떻게 진행 하 느 냐 하 는 것 입 니 다.
뿌리 찾기 에 있어 하 나 는 나무의 중심 이 두 개 이상 이기 때문에 두 나무 가 같은 구조 라면 중심 은 똑 같 을 것 입 니 다. 그래서 중심 부터 d f s dfs dfs dfs 를 시작 합 니 다.
d f s dfs dfs 에 대해 매번 d f s dfs dfs 가 한 노드 에 도착 할 때마다 모든 하위 트 리 의 괄호 서열 을 정렬 한 다음 에 순서대로 뿌리의 괄호 서열 을 추가 합 니 다.
v e c t o r vector vector 를 사용 하 는 것 이 좋다 고 들 었 습 니 다. 하지만 s t r i n g string string 을 직접 사용 하 는 것 도 좋 습 니 다. n, m 가 가장 크 기 때문에 50 입 니 다.
【 코드 】

#include
#include
#include
#include
#define N 1005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,t,num;
int Max[N],size[N];
int first[N],v[N],nxt[N];
string rec[N],brackets[N];
void add(int x,int y)
{
	t++;
	nxt[t]=first[x];
	first[x]=t;
	v[t]=y;
}
void find(int x,int father)
{
	int i,j;
	Max[x]=0,size[x]=1;
	for(i=first[x];i;i=nxt[i])
	{
		j=v[i];
		if(j!=father)
		{
			find(j,x);
			size[x]+=size[j];
			Max[x]=max(Max[x],size[j]);
		}
	}
	Max[x]=max(Max[x],n-size[x]);
	num=min(num,Max[x]);
}
void dfs(int x,int father)
{
	int i,j,num=0;
	string temp[N];
	brackets[x]='(';
	for(i=first[x];i;i=nxt[i])
	{
		j=v[i];
		if(j!=father)
		{
			dfs(j,x);
			temp[++num]=brackets[j];
		}
	}
	sort(temp+1,temp+num+1);
	for(i=1;i<=num;++i)
	  brackets[x]+=temp[i];
	brackets[x]+=')';
}
int main()
{
	int i,j,x;
	scanf("%d",&m);
	for(i=1;i<=m;++i)
	{
		t=0;
		scanf("%d",&n);
		memset(first,0,sizeof(first));
		for(j=1;j<=n;++j)
		{
			scanf("%d",&x);
			if(x)  add(x,j),add(j,x);
		}
		num=inf,find(1,0);
		string s=" ";
		for(j=1;j<=n;++j)
		{
			if(Max[j]==num)
			{
				dfs(j,0);
				if(s==" "||s>brackets[j])
				  s=brackets[j];
			}
		}
		rec[i]=s;
		for(j=1;j<=i;++j)
		{
			if(s==rec[j])
			{
				printf("%d
",j);
				break;
			}
		}
	}
	return 0;
}