这是错误代码:
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