Cod sursa(job #515142)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 20 decembrie 2010 15:22:31
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 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];
int ss[Nmax];
int ord[Nmax];
int q1[Nmax];
int q2[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 ;
	ord[++ord[0]]=nod;
	//c[nod]+=s;
	viz[nod]=1;
	q1[nod]=ord[0];	
	for(it=v[nod].begin();it!=v[nod].end();++it) {
		if (viz[*it])
			continue;
		dfs(*it);
	}
	ord[++ord[0]]=nod;
    q2[nod]=ord[0]+1;	
}

int query(int X){
	int suma=0;
	for (int i=1;i<=ord[0];++i){
		suma+=ss[i];
		if (suma==X)
			return ord[i];
	}
	return -1;
}

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);
		v[a].pb(b);
		v[b].pb(a);
	}
	
	dfs(1);
	ord[1]=-1;
	ord[0]=1;
	for (i=1;i<=m;++i)
	{
		scanf("%d", &tip);
		
		if (tip==1)
		{
			scanf("%d %d", &p, &s);
			ss[q1[p]]+=s;
			ss[q2[p]]-=s;
		}
		else
		if (tip==2)
		{
			scanf("%d", &s);
			printf("%d\n", query(s));
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}