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

· · 题解

Problem

给定一个以 1 为根，大小为 n 的有根树 T，需要找到一棵满足宽度单调不减的导出子树中最大的一棵。

Solve

从根节点往下决策是很麻烦的，因为他的儿子数量是不固定的，意思是说，在决策一个以 u 为根的子树的时候，你无法知道下一层的节点选几个和选那些最优。因为你的心胸太狭隘，无法纵观大局。

但是倒着考虑会好想些。首先，在某一层选满肯定是最优的，不过，并不是哪一层最宽就全选哪层，假如有一个很高的树，在第二层特别的宽。你选了这一层，然后发现你只能选一二层的点。而次宽的层在很深很深的地方，如果你选了次宽的层，然后其父亲，爷爷，曾爷爷辈都可以被选到，显然，能构造出一组使得其假掉的例子。

所以，全选哪一层无法确定，那就枚举哪一层全选，取最优。但是这样，时间复杂度就是 O(n^2) 的。

我们又发现，父亲的数量一定不会比儿子多，也就是说，可选层的点的数量也是呈单调态。因此，我们维护一个单调递增的栈，每一次跳到第一个小于这一个层的父辈层，之间的层的点数就是这一层与第一个小于这一个层的父辈层之间的层数再乘上第一个小于这一个层的父辈层的点数。最后取个最优方案即可。

Code

#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007

using namespace std;

inline int read() {
  rint x=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
  return x*f;
}

void print(int x){
  if(x<0){putchar('-');x=-x;}
  if(x>9){print(x/10);putchar(x%10+'0');}
  else putchar(x+'0');
  return;
}

const int N = 1e6 + 10;

struct Node {
  int v, nx;
} e[N << 1];

int n, h[N], tot, dep[N], stk[N], top, d[N], mx, ans, f[N], vis[N], sum[N]; 

void add(int u, int v) {
  e[++tot].v = v;
  e[tot].nx = h[u];
  h[u] = tot;
}

void dfs(int x, int fa) {
  dep[x] = dep[fa] + 1;
  mx = max(mx, dep[x]);
  d[dep[x]]++;
  for (int i = h[x]; i; i = e[i].nx) {
    int y = e[i].v;
    if(y == fa) continue;
    dfs(y, x);
  } 
}

signed main() {
  n = read();
  For(i,1,n-1) {
    int u = read(), v = read();
    add(u, v); add(v, u);
  }
  dep[0] = 0; 
  dfs(1, 0);
  For(i,1,n) {
    while(top && d[stk[top]] >= d[i]) top--;
    stk[++top] = i;
    sum[stk[top]] = sum[stk[top-1]] + d[stk[top]] * (stk[top] - stk[top-1]);
    ans = max(ans, sum[stk[top]]);
  }
  cout << ans << '\n';
  return 0;
}