蓬莱「凯风快晴 −富士火山−」（单调栈优化）

蓬莱「凯风快晴　−富士火山−」

通过观察，很容易想到：

1. 第 i i i 层的结点数如果比第 i + 1 i+1 i+1 层更多，一定可以去掉若干第 i i i 层的节点，使得结点数与第 i + 1 i+1 i+1 层一样多。

2. 不一定最下面一层的结点数最多，极端情况下，最下面一层如果只有 1 1 1 个结点，会限制上面每一层都只能取 1 1 1 个结点，很有可能得不到最优解。

3. 先用 d f s dfs dfs 求出每一层结点数，然后使用单调栈优化，分别求出使用第 i i i 层作为最后一层时的最优解，并求出其中的最大值即可。

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5 + 7;
vector<int> vc[N];
int depth, dpt[N], lves[N];
struct Node { int x, id, s; } stk[N];
void dfs(int u, int fa) {
	dpt[u] = dpt[fa] + 1, ++lves[dpt[u]];
	depth = max(depth, dpt[u]);
	for (auto v : vc[u])
		if (v != fa)
			dfs(v, u);
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		vc[u].emplace_back(v), vc[v].emplace_back(u);
	}
	dfs(1, 0);
	int mx = 0, tp = 0;
	// 使用单调栈求出最大值
	for (int i = 1; i <= depth; ++i) {
		while (tp && stk[tp].x>lves[i]) --tp;
		int s = stk[tp].s + (i-stk[tp].id)*lves[i];
		mx = max(s, mx);
		stk[++tp] = {lves[i], i, s};
	}
	printf("%d", mx);
}