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

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

通过观察，很容易想到：

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

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

3. 先用 $dfs$ 求出每一层结点数，然后使用单调栈优化，分别求出使用第 $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);
}