Poderiam me ajudar com uma questão sobre arborescência da OBI?

[Juliano Balcante Pereira]

Percebi que a questão móbile era parecida com a questão família real, era sobre arborescência. O que muda é o processamento dos dados internos.

Segue a questão móbile:

 

MÓBILE

Móbiles são objetos muito populares hoje em dia, sendo encontrados até em berços, para diversão de bebês, mas foram concebidos há muito tempo (em 1931) pelo então jovem artista americano Alexander Calder como esculturas em movimento. Um móbile é uma estrutura composta de peças unidas por fios. O móbile é preso por um fio a uma argola pela qual ele é suspenso, permitindo que a estrutura movimente-se livremente. A argola é presa a uma única peça, chamada de peça-raiz do móbile. A peça-raiz pode ter zero ou mais sub-móbiles pendurados nela, cada sub-móbile sendo composto por uma peça-raiz na qual por sua vez podem estar pendurados zero ou mais sub-móbiles, e assim sucessivamente. Abaixo podemos ver dois exemplos de móbiles:

Victor é dono de uma fabrica de móbiles que emprega centenas de artesãos. Cada móbile produzido na fábrica é confeccionado por um artesão, que cria móbiles de acordo com o seu gosto pessoal, utilizando peças de formatos distintos. Entretanto, Victor tem notado que nem todos os seus artesãos possuem a mesma habilidade artística, de forma que às vezes o móbile produzido nem sempre é bem balanceado, segundo a sua concepção. Para Victor, um móbile é bem balanceado se, para cada peça, todos os sub-móbiles pendurados nela são compostos pelo mesmo número de peças. O número de peças de um sub-móbile é determinado contando-se o número de peças que o compõe, incluindo a sua peça-raiz. Note que cada peça do móbile, exceto a peça-raiz, é pendurada em exatamente uma outra peça.

Por exemplo, o móbile da figura (a) acima é um móbile bem balanceado: a peça-raiz possui um único sub-móbile, que por sua vez possui três sub-móbiles, todos com o mesmo número de peças (uma única). Já o móbile da figura ( é um móbile mal balanceado: a peça-raiz possui dois sub-móbiles, um com o total de duas peças e outro com o total de uma peça.

 

Tarefa

Dada a descrição de um móbile, você deve escrever um programa para determinar se o móbile está bem balanceado ou não.

 

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica o número de peças utilizadas no móbile (1 ≤ N ≤ 10.000). As peças são identificadas por inteiros de 1 a N . Cada uma das N linhas seguintes contém dois números inteirosI e J , indicando que a peça de número I está pendurada na peça de número J (a peça raiz está pendurada na argola, que é identificada pelo o número 0).

 

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo a palavra bem se o móbile estiver bem balanceado ou mal caso esteja mal balanceado. A palavra deve ser escrita com todas as letras em minúsculas.

Exemplos Entrada

31 02 13 2			

Saída

bem			

Entrada

51 02 14 23 25 2			

Saída

bem			

Entrada

72 01 23 14 35 46 47 5			

Saída

mal		

Agora a questão família real:

FAMÍLIA REAL

O rei de um reino muito muito distante deu uma grande festa para reunir todas as gerações dos seus descendentes: filhos e filhas, netos e netas, bisnetos e bisnetas, e assim por diante. Ele, que gosta muito de estatísticas, agora quer saber, para cada geração, qual a porcentagem de descendentes daquela geração que compareceu à festa. Você foi contratado para escrever um programa de computador que calcule as porcentagens de todas as gerações! O rei tem N descendentes, identificados com os números de 1 a N. O próprio rei será identificado com o número 0. Será dada apenas a informação, para cada  descendente, de quem é o seu pai ou sua mãe, na linha de descendência que começa no rei. Além disso, claro, será dada a lista de todos que compareceram à festa.

 

Entrada

A primeira linha da entrada contém dois inteiros N e M, respectivamente, o número de descendentes e o número de participantes da festa. A segunda linha contém N números, representando os pais ou mães dos N descendentes, em ordem crescente: o primeiro número indica o pai ou a mãe do descendente de número 1, o segundo número indica o pai ou a mãe do descendente de número 2, e assim por diante. A terceira linha contém M números, identificando todos os descendentes que compareceram à festa.

 

Saída

Seu programa deve imprimir uma linha com uma lista de números reais, com precisaão de duas casas decimais, indicando a porcentagem, para cada  geração, dos descendentes daquela geração que compareceram à festa. O primeiro número deve ser a porcentagem dos filhos e filhas, o segundo dos

netos e netas, e assim por diante.

 

Restrições

1 <= M <= N <=10000

 

Exemplos

 

Entrada

9 57 3 0 9 0 3 5 6 73 2 8 1 9

Saída

50.00 33.33 100.00 0.00		

 

Entrada

16 11

15 9 2 8 6 11 0 3 0 8 12 0 9 6 16 12

5 14 9 12 6 2 4 10 3 11 7

Saída

100.00 50.00 66.67 50.00 100.00		

 

 

 

Então eu peguei uma solução disponível na internet e funcionou, acho que usaram recursão para melhorar a eficiência.

Olha o código:

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10000int	p[MAXN + 1];int	n;int	bem;int rec(int r);int main (){	int	i,j,k;	scanf("%d", &n);		for (k = 0; k < n; k++){		scanf("%d%d", &i, &j);		p[i] = j;	}	bem = 1;	rec(0);	if(bem==1){		printf("bem\n");	}	else{		printf("mal\n");	}	return 0;}int rec (int r){	int	q,	/* Quantidade de peças em cada sub-móbile de r. */		t,	/* Quantidade de peças total no móbile r. */		s;	int	i;		q = -1;	t = 1;	for (i = 1; i <= n; i++){		/* Procura pelos móbiles cujo pai é r. */		if (p[i] != r){			continue;		}		/* Calcula a quantidade de peças no sub-móbile i. */		s = rec(i);		t += s;//quantida		/* Primeiro sub-móbile de r. */		if (q == -1){			q = s;			continue;		}		/* Verifica se o sub-móbile atual i tem a mesma		   quantidade de peças que o sub-móbile anterior. */		if (s != q){			bem = 0;		}	}	return t;}

Bem, tentei utilizar esse código como base e fazer algumas alterações: 

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10100int p[MAXN];//vetor de pais de vetor[i]int n,m;int bem;int rec(int r);int main(){	int i,j,k;	int pre[MAXN];		scanf("%d%d",&n,&m);	for(i=0;i<n;i++){		scanf("%d",&j);		p[i]=j;	}	for(i=0;i<m;i++){		scanf("%d",&j);		pre[i]=j;	}		rec(0);	return 0;}int rec(int r){	int q;	int t;	int s;		int i;		q=-1;	t=1;	for(i=1;i<=n;i++){		if(p[i]!=r){			continue;		}		s=rec(i);		t+=s;						//....... ainda nao terminei	}	return t;}

OBS.: Como não sei o termo correto e árvore genealógica parece um móbile, o que eu chamar de móbile no próximo parágrafo significa o "pai".

Segundo o autor do 1º código, na parte dentro da função rec(int r) que chama ela mesma é para calcular a quantidade de peças do mobile r

Eu posso até utilizar a quantidade de peças do mobile r no final para achar a porcentagem, mas como eu poderia armazenar os filhos do pai r para que eu possa comparar com o vetor de presentes e calcular a porcentagem? Eu pensei em utilizar um vetor para armazenar os "filhos" do pai e a quantidade de filhos do móbile r