警钟长鸣(如果你WA#3)
查看原帖
警钟长鸣(如果你WA#3)
549846
dpACerFXing楼主2024/12/8 23:22

这是错误代码:

void dfs(int u, int fa) {
	dp[u]=a[u];
	for(int i=head[u]; i; i=edge[i].next) {
		int v=edge[i].v;
		if(v==fa) continue ;
		dfs(v, u);
		if(dp[v]>0) dp[u]+=dp[v];
	}
	ans=max(ans, dp[u]);
}

if(dp[v]>0) dp[u]+=dp[v];

一行提到循环外面即可AC

原因:有可能ans最大值在叶子结点取到,此时程序不会进入循环,所以不会更新ans

2024/12/8 23:22
加载中...