题解：AT_abc394_f [ABC394F] Alkane

思路

这道题是一个树形

DP

。

状态

dp_{u,i}

为以

u

为根节点，有

i

个子节点，最大节点个数。因为最多只能有四个，所以不会炸。

初始化

dp_{u,0}

是

1

就是它本身。其它的就为无穷小。

转移方程

dp_{u,i}=max(dp_{u,i},dp_{u,i-1}+max(dp_{v,0},dp_{v,3}))

。

也就是说它可以选择加这个儿子或不加。要加的话就必须从儿子有三个或零个子节点中选，不然就不满足要求。由此可以推出此方程

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int n,h[414514],e[414514],ne[414514],idx,dp[414514][5],mx=-1;
void add(int u,int v){
	e[idx]=v,ne[idx]=h[u],h[u]=idx++;
} 
void dfs(int u,int pre){
	dp[u][1]=-0x3f3f3f3f,dp[u][2]=-0x3f3f3f3f,dp[u][3]=-0x3f3f3f3f,dp[u][4]=-0x3f3f3f3f;
	dp[u][0]=1;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==pre){
			continue;
		}
		dfs(j,u);
		for(int i=4;i>=1;i--){
			dp[u][i]=max(dp[u][i],dp[u][i-1]+max(dp[j][0],dp[j][3]));
		}
	}
	if(dp[u][1]>2){
		mx=max(mx,dp[u][1]);
	} 
	mx=max(mx,dp[u][4]);
}
int main(){
	memset(h,-1,sizeof(h));
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	cout<<mx;
	return 0;
}

题解：AT_abc394_f [ABC394F] Alkane

文章操作

思路

状态

初始化

转移方程

Code

相关推荐

评论

题解：AT_abc394_f [ABC394F] Alkane