题目大意

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

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

分析

想要最优，对于单独的一层显然全取最优，所以我们定义

dp_i

为第

i

层全取的最大导出子树大小。

于是我们枚举层数，确定全选哪一层，取最优此时复杂度为

O(n^2)

。

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

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

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

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

时间复杂度瓶颈在于第一遍搜索处理点的信息，后边转移复杂度为树的层数。复杂度为

O(n)

可以通过。

代码

CPP

#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;
}

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

文章操作

题目大意

分析

代码

相关推荐

评论

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