Cod sursa(job #846475)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 2 ianuarie 2013 12:02:40
Problema Arbore Scor 5
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.7 kb
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;

const int N = 100011;
const int VMAX = 1000001;
const int SIZE = 320;

int nr, n, m, conv[N], cd[N], ord[N], pl[SIZE], val[N];
vector<int> v[N];
bool ver[N];
map<int, int> h[SIZE];

void df(int nod) {
	ver[nod] = 1;
	
	conv[nod] = nr;
	ord[nr] = nod;
	++nr;
	
	for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
		if(!ver[*it])
			df(*it);
	
	cd[nod] = nr - 1;
}

void make() {
	
	for(int i = 0; i < nr; i++) {
		h[i/SIZE][0]++;
	}
}

void add(int cs, int cd, int va) {
	int i = cs;
	
	while(i <= cd && i % SIZE != 0) {
		int b = i / SIZE;
		
		h[b][val[i]]--;
		val[i] += va;
		h[b][val[i]]++;
		
		++i;
	}
	
	while(i + SIZE - 1 <= cd) {
		int b = i / SIZE;
		
		pl[b] += va;
		
		i += SIZE;
	}
	
	while(i <= cd) {
		int b = i / SIZE;
		
		h[b][val[i]]--;
		val[i] += va;
		h[b][val[i]]++;
		
		++i;
	}
}

int query(int sum) {
	
	for(int i = 0, j = 0, s2; i < nr; i += SIZE, ++j) {
		s2 = sum - pl[j];
		
		if(s2 < 0)
			continue;
		
		if(h[j][s2]) {
			
			for(int k = i; k < i + SIZE; ++k)
				if(val[k] == s2)
					return ord[k];
		}
		
	}
	return -1;
}

int main() {
	int i, a, b, op;
	
	freopen("arbore.in", "r", stdin);
	freopen("arbore.out", "w", stdout);
	
	cin >> n >> m;
	
	for(i = 1; i != n; ++i) {
		scanf("%d%d", &a, &b);
		
		v[a].push_back(b);
		v[b].push_back(a);
	}
	
	df(1);
	
	make();
	
	for(i = 1; i<=n; ++i) {
		scanf("%d", &op);
		
		if(op == 1) {
			scanf("%d%d", &a, &b);
			add(conv[a], cd[a], b);
		}
		else {
			scanf("%d", &b);
			printf("%d\n", query(b));
		}
	}
	
	return 0;
}