centroides-2.cpp

#include <iostream>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

int tree_size(int s, int parent, vector<set<int>> &G) {
	int count = 1;
	for(int t : G[s])
	if(t != parent) {
		count += tree_size(t, s, G);
	}
	return count;
}

tuple<int, int> scentroid(int s, int parent, vector<set<int>> &G, int n) {
	int cent_ret = s;
	int count = 1;

	for(int t : G[s]) {
		if(t != parent) {
			int cent_t, count_t;
			tie(cent_t, count_t) = scentroid(t, s, G, n);

			if(count_t > (n/2)) {
				cent_ret = cent_t;
			}
			count += count_t;
		}
	}
	return make_tuple(cent_ret, count);
}

int centroid(int s, vector<set<int>> &G) {
	int cent, count;
	tie(cent, count) = scentroid(s, -1, G, tree_size(s, -1, G));
	return cent;
}

// Rajoute la distance à un parent pour tous ses descendant
void update_dists(int dist, int s, int prev, vector<set<int>> &G, vector<vector<int>> &dist_parent) {
	dist_parent[s].push_back(dist);
	for(int t : G[s])
	if(t != prev) {
		update_dists(dist+1, t, s, G, dist_parent);
	}
}

// Construit l'arbre de centroides (sous forme de tableau du père)
int make_gc(int s, vector<set<int>> &G, vector<int> &parent, vector<vector<int>> &dist_parent) {
	int cent = centroid(s, G);

	vector<int> fils;
	for(int t : G[cent])
		fils.push_back(t);
	
	for(int t : fils) {
		update_dists(1, t, cent, G, dist_parent);
		G[t].erase(cent);
		G[cent].erase(t);

		int tc = make_gc(t, G, parent, dist_parent);
		parent[tc] = cent;
	}
	return cent;
}

// Colore un sommet en rouge
void update_red(int s, vector<int> &parent, vector<vector<int>> &dist_parent, vector<int> &red_dist) {
	red_dist[s] = 0;

	int k = s;
	int i = dist_parent[s].size();
	while((k = parent[k]) != -1) {
		i--;
		if(red_dist[k] == -1 || red_dist[k] > dist_parent[s][i]) // dist_parent[s][i] = distance(s, k)
			red_dist[k] = dist_parent[s][i];
	}
}

// Retourne la distance du sommet rouge le plus proche
int rdist(int s, vector<int> &parent, vector<vector<int>> &dist_parent, vector<int> &red_dist) {
	int dmin = red_dist[s] != -1 ? red_dist[s] : parent.size();
	int k = s;
	int i = dist_parent[s].size();
	while((k = parent[k]) != -1) {
		i--;
		if(red_dist[k] != -1 && red_dist[k] + dist_parent[s][i] < dmin) // dist_parent[s][i] = distance(s, k)
			dmin = red_dist[k] + dist_parent[s][i];
	}
	return dmin;
}

int main() {
	int N, M;
	cin >> N >> M;

	vector<set<int>> G(N);
	int s, t, v;
	for(int i=0 ; i < N-1 ; i++) {
		cin >> s >> t;
		s--; t--;
		G[s].insert(t);
		G[t].insert(s);
	}


	vector<int> parent(N, -1);
	vector<vector<int>> dist_parent(N);
	vector<int> red_dist(N, -1);

	make_gc(0, G, parent, dist_parent);
	update_red(0, parent, dist_parent, red_dist);

	for(int i=0 ; i < M ; i++) {
		cin >> t >> v;
		if(t == 1) {
			update_red(v-1, parent, dist_parent, red_dist);
		}
		else if(t == 2) {
			cout << rdist(v-1, parent, dist_parent, red_dist) << endl;
		}
	}
}

// http://codeforces.com/problemset/problem/342/E