POI #树上问题 #贪心

考虑什么样的点合法，这个点需要尽可能的均匀的子树，手摸几个发现，当且仅当这个点是重心的时候是可行的

那么贪心的来说，我们希望最后一个不需要回来的路径长度尽可能的大，搜索就可以做到

特判当有一个子树的 \(siz\) 为 \(\frac{n}{2}\) 时，最后的路径一定在这棵树内

// Author: xiaruize
const int N = 1e6 + 10;

int n;
vector<int> g[N];
vector<int> vec;
int siz[N];
int son[N];
int ct[2];
int anc[N];
int res = 0;
int sum = 0, mxdep = 0;

void dfs(int x, int fa)
{
	anc[x] = fa;
	siz[x] = 1;
	int mx = 0;
	for (auto v : g[x])
	{
		if (v == fa)
			continue;
		dfs(v, x);
		siz[x] += siz[v];
		mx = max(mx, siz[v]);
	}
	mx = max(mx, n - siz[x]);
	if (mx * 2 <= n)
		ct[ct[0] != 0] = x;
}

void dfs2(int x, int fa, int dep)
{
	sum += dep;
	mxdep = max(mxdep, dep);
	for (auto v : g[x])
	{
		if (v == fa)
			continue;
		dfs2(v, x, dep + 1);
	}
}

void solve()
{
	cin >> n;
	rep(i, 1, n - 1)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, 0);
	rep(i, 1, n)
	{
		if (i != ct[0] && i != ct[1])
			cout << "-1\n";
		else
		{
			sum = mxdep = 0;
			// dfs(i, 0);
			int fl = -1;
			if (n == siz[i] * 2)
			{
				dfs2(anc[i], i, 1);
				int t = mxdep;
				dfs2(i, anc[i], 0);
				cout << sum * 2 - t << '\n';
			}
			else
			{
				int p = -1;
				for (auto v : g[i])
				{
					if (siz[v] * 2 == n)
						p = v;
				}
				if (p == -1)
				{
					dfs2(i, 0, 0);
					cout << sum * 2 - mxdep << endl;
					continue;
				}
				dfs2(p, i, 1);
				int t = mxdep;
				dfs2(i, p, 0);
				cout << sum * 2 - t << endl;
			}
		}
	}
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}