Cod sursa(job #340575)

Utilizator savimSerban Andrei Stan savim Data 15 august 2009 14:15:16
Problema Arbore Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define MAX_N 100010

int n, m, tip, p, q, s, ok;
int fol[MAX_N], add[MAX_N];
vector <int> A[MAX_N];

void df(int nod, int sum) {
	fol[nod] = 1;
	int len = A[nod].size();

	if (sum == s && !ok) {
    	printf("%d\n", nod);
		ok = 1;
	}

	for (int i = 0; i < len; i++)
		if (!fol[A[nod][i]])
			df(A[nod][i], sum + add[A[nod][i]]);

	fol[nod] = 0;
}

int main() {

	freopen("arbore.in", "r", stdin);
	freopen("arbore.out", "w", stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &p, &q);
		A[p].push_back(q);
		A[q].push_back(p);
	}

	for (int i = 1; i <= m; i++) {
		scanf("%d", &tip);
		if (tip == 1) {
			scanf("%d %d", &p, &s);
			add[p] += s;
		}
		else {
			ok = 0;
        	scanf("%d", &s);
			df(1, add[1]);
		}
	}

	return 0;
}