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

· · 题解

题目大意

导出子树 ：可以有节点不选的“子树”。

找到一棵最大的满足宽度单调不减的导出子树的大小。

分析

想要最优，对于单独的一层显然全取最优，所以我们定义 dp_i 为第 i 层全取的最大导出子树大小。

于是我们枚举层数，确定全选哪一层，取最优此时复杂度为 O(n^2)。

考虑省掉确定全选层数后取最优的时间复杂度。

定义易得最后的导出子树每层宽度单调不减，我们考虑维护一个具有单调性的数据结构：单调栈里面存层的宽度。

我们让栈中元素单调递增对于新的全选的一层，它从次栈顶（上一次选择的）宽度转移，新增的点数为：这一层与次栈顶之间的层数再乘上这一层的点数。在过程中取最优。

我们需要处理出来的信息就只有，每个点的层数，和每个层数的点数。

时间复杂度瓶颈在于第一遍搜索处理点的信息，后边转移复杂度为树的层数。复杂度为 O(n) 可以通过。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

struct E{
    int to,ne;
}e[N*2];

int n,d[N],dp[N],dep[N],stk[N],top,h[N],cnt,mx,ans;

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

void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    d[dep[u]]++;
    mx=max(mx,dep[u]);
    for(int i=h[u];~i;i=e[i].ne){
        int v=e[i].to;
        if(v==fa)continue;
        dfs(v,u);
    } 
}

int main(){
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dep[0]=0;
    dfs(1,0);
    for(int i=1;i<=mx;i++){
        while(top&&d[stk[top]]>=d[i])top--;
        stk[++top]=i;
        dp[stk[top]]=dp[stk[top-1]]+d[stk[top]]*(stk[top]-stk[top-1]);
        ans=max(ans,dp[stk[top]]);
    }
    printf("%d",ans);
    return 0;
}