85NybJ - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;
int n, ans = 2e9;
vector <int> e[200010];
int fa[200010], s[200010];
int calc(int u, int v, int w)
{
	return max(max(u, v), w) - min(min(u, v), w);
}
void find_fa(int y, int x)
{
	fa[y] = x;
	for (auto z : e[y]) if (z != x) find_fa(z, y);
}
void find_size(int x)
{
	for (auto y : e[x]) if (y != fa[x])	find_size(y);
	s[x] = 1;
	for (auto y : e[x]) if (y != fa[x]) s[x] += s[y];
}
multiset <int> s1, s2;
void insert_tree(int x)
{
	s1.insert(s[x]);
	for (auto y : e[x]) if (y != fa[x]) insert_tree(y);
}
void work_sep(int x)
{
	if (!s1.empty())
	{
		int u = s[x], v, w;
		int v1 = *(--s1.upper_bound((n - s[x]) / 2));
		int v2 = *s1.lower_bound((n - s[x] + 1) / 2);
		if (abs(2 * v1 - n + s[x]) < abs(2 * v2 - n + s[x])) v = v1;
		else v = v2;
		w = n - u - v;
        cout << x << " | ";
        for (auto temp : s1) cout << temp << " ";
        cout << endl;
		ans = min(ans, calc(u, v, w));
		cout << "/" << u << " " << v << " " << w << endl;
	}
	for (auto y : e[x])
	{
		if (y != fa[x])
        {
			work_sep(y);
    		insert_tree(y);
        }
	}
}
void work_anc(int x)
{
	if (!s2.empty())
	{
		int u = s[x], v, w;
		int v1 = *(--s2.upper_bound((n - s[x]) / 2 + s[x]));
		int v2 = *s2.lower_bound((n - s[x] + 1) / 2 + s[x]);
		if (v1 == 0) v1 = 2e9;
		if (v2 == 0) v2 = 2e9;
		if (abs(2 * v1 - n - s[x]) < abs(2 * v2 - n - s[x])) v = v1 - u;
		else v = v2 - u;
		w = n - u - v;
		// cout << x << " | " << u << " " << v << " " << w << endl;
		ans = min(ans, calc(u, v, w));
	}
	s2.insert(s[x]);
	for (auto y : e[x]) if (y != fa[x]) work_anc(y);
	s2.erase(s2.find(s[x]));
}
int main()
{
	cin >> n;
	for (int x, y, i = 1; i < n; i++)
	{
		cin >> x >> y;
		e[x].push_back(y); e[y].push_back(x);
	}
	find_fa(1, 0);
	find_size(1);
	work_sep(1);
	work_anc(1);
	cout << ans;
	return 0;
}