GYM 101673F（树计数）

树上每个割点计算一下各个size的组合相乘再相加为第一问答案，取最大的；再把本答案中最大的两个size相乘减掉，为第二问答案。

const int maxn = 1e4 + 5;

int n, size[maxn], ans, b;

vector<int> adj[maxn];

void dfs(int cur, int fa) {

	size[cur] = 1;

	vector<int> v;

	for (auto i : adj[cur]) {

		if (i == fa)	continue;

		dfs(i, cur);

		size[cur] += size[i];

		v.push_back(size[i]);

	}

	if (v.empty())	return;

	v.push_back(n - size[cur]);

	sort(v.begin(), v.end());

	int tmp = 0;

	for (auto i : v) {

		tmp += i * (n - i - 1);

	}

	if (ans < tmp / 2) {

		ans = tmp / 2, b = ans - v.back() * v[v.size() - 2];

	}

}

int main() {

	read(n);

	rep(i, 1, n) {

		int u, v;

		read(u), read(v);

		adj[u].push_back(v);

		adj[v].push_back(u);

	}

	n++;

	dfs(0, -1);

	printf("%d %d\n", ans, b);

	return 0;

}

巴特西

GYM 101673F（树计数）

最新文章

热门文章