Cod sursa(job #29356)

Utilizator butyGeorge Butnaru buty Data 9 martie 2007 09:25:17
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<stdio.h>
const int Nmax=100000;
struct lista
{
	int inf,x,sb;
	lista *urm;
};
int main()
{
	lista *C[Nmax],*cd1,*cd2,*c;
	lista *A[Nmax];
	freopen("arbore.in","r",stdin);
	freopen("arbore.out","w",stdout);
	int x,y,i,N,M,X[Nmax],sb[Nmax];
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)
	{
		A[i]=new lista;
		A[i]->urm=NULL;
		X[i]=sb[i]=0;
		C[i]=A[i];
	}
	for(i=1;i<N;i++)
	{
		scanf("%d%d",&x,&y);
		C[x]->urm=new lista;
		C[x]=C[x]->urm;
		C[x]->inf=y;
		C[x]->urm=NULL;
	}

	for(i=1;i<=M;i++)
	{
		scanf("%d",&x);
		if(x==1)
		{
			scanf("%d%d",&x,&y);
			X[x]+=y;
			sb[x]+=y;
		}
		else
		{
			scanf("%d",&x);
			y=0;
			cd1=new lista;
			cd1->inf=1;
			cd1->urm=NULL;
			cd2=cd1;
			if(X[cd1->inf]==x)
				y=1;
			while(cd1&&y==0)
			{
				for(c=A[cd1->inf]->urm;c&&y==0;c=c->urm)
				{
					X[c->inf]+=X[cd1->inf];
					sb[c->inf]+=sb[cd1->inf];
					if(X[c->inf]==x)
						y=c->inf;
					cd2->urm=new lista;
					cd2=cd2->urm;
					cd2->inf=c->inf;
					cd2->urm=NULL;
				}
				sb[cd1->inf]=0;
				c=cd1;
				cd1=cd1->urm;
				delete c;
			}
			if(y)
				printf("%d\n",y);
			else
				printf("%d\n",-1);
		}

	}
	return 0;
}