Cod sursa(job #515123)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 20 decembrie 2010 14:22:12
Problema Arbore Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

#define file_in "arbore.in"
#define file_out "arbore.out"

#define Nmax 101000
#define pb push_back

int n,m,p,s,c[Nmax];
vector<int> v[Nmax];
int a,b;
int j,tip;
int viz[Nmax];

void dfs(int nod)
{
	int i;
	//vector<int> :: iterator it;
	if (viz[nod]) return ;
	c[nod]+=s;
	viz[nod]=1;
	
	for (i=0;i<v[nod].size();++i)
		if (!viz[v[nod][i]])
		    dfs(v[nod][i]);
}

int main()
{
	int i ;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	
	for (i=1;i<n;++i)
	{
		scanf("%d %d", &a,&b);
		if (a<b)
			v[a].pb(b);
		else
			v[b].pb(a);
	}
	
	memset(c,0,sizeof(c));
	while(m--)
	{
		scanf("%d", &tip);
		
		if (tip==1)
		{
			memset(viz,0,sizeof(viz));
			scanf("%d %d", &p, &s);
			dfs(p);
			
			/*for(i=1;i<=n;++i)
				printf("%d ", c[i]);
			printf("\n");*/
		}
		else
		if (tip==2)
		{
			int ok=1;
			scanf("%d", &s);
			for (i=1;i<=n && ok;++i)
				 if (c[i]==s)
					 printf("%d\n",i),
					 ok=0;
			if (ok) printf("-1\n");		 
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}