【NOIP2019提高组正式赛day2】树的重心（centroid）

On contest

考场打了(55)分暴力分（其实应该能拿(75)的，但我没打）

Solution

现在听了讲，发现这道题其实也并非那么难的。
首先我们要知道几个性质：
1.重心最多只有两个。
2.重心一定是从根跳重儿子一直跳到某个位置。
对于1显然。
对于2的话，假设重心是一个轻儿子(x)，那么(siz[x])一定小于(siz[son[fa[x]]])，再加上(fa[x])及以上的点肯定大于整个树的节点数的一半，那么(x)一定不是重心了。

所以求一个数的重心，我们可以从根一直倍增在满足条件的情况跳，那么跳到的最终点(x)一定是重心，而(fa[x])则可能是重心。

所以我们可以枚举要删的边。
我们发现，对于删的边的下面求重心，没有影响，就跳重儿子就可以了。
但对于删的边的上面，那就有点问题了。
我们发现，上面树的重边可能会发生改变（因为下面删了一个子树）。
所以我们要先强制上面的不跳到下面去，然后再看看跳次重儿子（也就是可能变成重儿子的点）是否能满足条件。

如此即可。

Code

#include <cstdio>
#include <cstring>
#define N 300010
#define ll long long
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = (a); x <= (b); x++)
#define fd(x, a, b) for (int x = (a); x >= (b); x--)
using namespace std;
struct node{int v, fr;}e[N << 1];
int T, n, tail[N], fa[N], a[N][2], cnt = 0, number = 0;
int siz[N], dep[N], dfn[N], son[N][21], cson[N];
ll ans = 0;

inline int read()
{
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

inline void add(int u, int v) {e[++cnt] = (node){v, tail[u]}; tail[u] = cnt;}

void dfs(int x)
{
	dfn[x] = ++number;
	siz[x] = 1, son[x][0] = cson[x] = 0;
	for (int p = tail[x], v; p; p = e[p].fr)
	{
		v = e[p].v;
		if (v == fa[x]) continue;
		dep[v] = dep[x] + 1, fa[v] = x;
		dfs(v), siz[x] += siz[v];
		if (siz[v] > siz[son[x][0]])
			cson[x] = son[x][0], son[x][0] = v;
		else if (siz[v] > siz[cson[x]]) cson[x] = v;
	}
	for (int i = 0; i <= 18; i++)
		son[x][i + 1] = son[son[x][i]][i];
}

void easy_query(int x, int tot)
{
	for (int i = 18; i >= 0; i--)
		if (son[x][i] && siz[son[x][i]] >= tot - siz[son[x][i]]) x = son[x][i];
	ans += x;
	if (siz[x] * 2 == tot) ans += fa[x];
}

int got(int x, int cnd) {return siz[x] - (dfn[cnd] >= dfn[x] && dfn[cnd] <= dfn[x] + siz[x] - 1 ? siz[cnd] : 0);}

void medium_query(int x, int tot, int cnd)
{
	int size;
	for (int i = 18; i >= 0; i--)
	{
		size = got(son[x][i], cnd);
		if (! son[x][i] || (dfn[son[x][i]] >= dfn[cnd] && dfn[son[x][i]] <= dfn[cnd] + siz[cnd] - 1)) continue;
		if (size >= tot - size) x = son[x][i];
	}
	size = siz[cson[x]];
	if (size >= tot - size)
	{
		x = cson[x];
		for (int i = 18; i >= 0; i--)
		{
			size = siz[son[x][i]];
			if (size >= tot - size) x = son[x][i];
		}
	}
	ans += x;
	size = got(x, cnd);
	if (size * 2 == tot) ans += fa[x];
}

void solve(int x)
{
	if (x != 1) easy_query(x, siz[x]);
//	solve son
	if (son[x][0])
	{
		medium_query(1, siz[1] - siz[son[x][0]], son[x][0]); 
		solve(son[x][0]);
	}
	for (int p = tail[x], v; p; p = e[p].fr)
	{
		v = e[p].v;
		if (v == fa[x] || v == son[x][0]) continue;
		medium_query(1, siz[1] - siz[v], v);
		solve(v);
	}
}

int main()
{
	freopen("centroid.in", "r", stdin);
	freopen("centroid.out", "w", stdout);
	T = read();
	while (T--)
	{
		mem(tail, 0); cnt = 0;
		ans = 0;
		n = read();
		fo(i, 1, n - 1)
		{
			a[i][0] = read(), a[i][1] = read();
			add(a[i][1], a[i][0]), add(a[i][0], a[i][1]);
		}
		dfs(1);
		solve(1);
		printf("%lld
", ans);
	}
	return 0;
}