My solution to QTREE3 (spoj.com)

solution.cpp

#include <bits/stdc++.h>

//#define file_stream
//#define debug

using namespace std;

const int MXN = 1e5 + 10;

vector <int> g[MXN], order, tmp[MXN];
bool used[MXN];
int sz[MXN], heavy[MXN], start[MXN], finish[MXN], pos[MXN], tree[MXN], path[MXN];
int p[MXN];
int n, m, hsz, curcolor;

struct tournament_tree {
	vector <int> a;
	void resize(int m){
		a.resize(4 * m, 0);
	}
	void upd(int ver, int tmp, int v, int tl, int tr){
		if(tl == tr)
			a[v] = a[v] ? 0 : tmp;
		else {
			int tm = (tl + tr) / 2;
			if(ver <= tm)
				upd(ver, tmp, v + v, tl, tm);
			else
				upd(ver, tmp, v + v + 1, tm + 1, tr);
			a[v] = a[v + v + 1] ? a[v + v + 1] : a[v + v];
		}
	}
	int get(int l, int r, int v, int tl, int tr){
		if(l > r)
			return 0;
		if(tl == l && tr == r)
			return a[v];
		int tm = (tl + tr) / 2;
		int b = get(l, min(r, tm), v + v, tl, tm),
			c = get(max(l, tm + 1), r, v + v + 1, tm + 1, tr);
		return c ? c : b;
	}
};

tournament_tree tt[MXN];

void dfs(int v, int par = 0){
	used[v] = true;
	p[v] = par;
	for(int i = 0; i < g[v].size(); i++){
		int to = g[v][i];
		if(!used[to]){
			dfs(to, v);
		}
	}
	order.push_back(v);
}

void hld_init(){
	dfs(1);
	memset(used, 0, sizeof(used));
	used[0] = 1;
	for(int i = 0; i < order.size(); i++){
		int v = order[i];
		if(!used[v]) {
			start[curcolor] = hsz;
			while(!used[v]){
				path[v] = curcolor;
				pos[v] = hsz - start[curcolor];
				tree[hsz++] = v;
				used[v] = true;
				v = p[v];
			}
			tt[curcolor].resize(hsz - start[curcolor]);
			finish[curcolor++] = hsz - 1;
		}
	}
}

int ans(int v){
	int tmp = 0, ret = 0, tmpsz;
	while(path[v] != path[1]){
		tmpsz = finish[path[v]] - start[path[v]];
		tmp = tt[path[v]].get(pos[v], tmpsz, 1, 0, tmpsz);
		if(tmp)
			ret = tmp;
		v = p[tree[finish[path[v]]]];
	}
	tmpsz = finish[path[v]] - start[path[v]];
    tmp = tt[path[v]].get(pos[v], tmpsz, 1, 0, tmpsz);
    if(tmp)
        ret = tmp;
    return  !ret ? -1 : ret;
}

int main(){
	#ifdef file_stream
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n - 1; i++){
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	hld_init();
	#ifdef debug
		for(int i = 0; i < curcolor; i++){
			for(int j = start[i]; j <= finish[i]; j++)
				printf("%d ", tree[j]);
			printf("\n");
		}
	#endif
	while(m--){
		int type, v;
		scanf("%d%d", &type, &v);
		if(type & 1)
			printf("%d\n", ans(v));
		else {
			tt[path[v]].upd(pos[v], v, 1, 0, finish[path[v]] - start[path[v]]);
			#ifdef debug
			for(int i = 1; i < tt[path[v]].a.size(); i++)
				printf("%d ", tt[path[v]].a[i]);
			printf("\n");
			#endif
		}
	}
	return 0;
}