最大子树和题目地址输入7-1-1-11110142536475767输出3题解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN16005;inta[N];intdp[N];intsum-N;vectorintedges[N];voiddfs(intu,intfa){dp[u]a[u];for(autoit:edges[u]){if(itfa)continue;dfs(it,u);if(dp[it]0){dp[u]dp[it];}}summax(dp[u],sum);}signedmain(){intn;cinn;for(inti1;in;i)cina[i];for(inti1;in;i){intu,v;cinuv;edges[u].push_back(v);edges[v].push_back(u);}dfs(1,1);coutsumendl;return0;}题目要求美丽指数之和是最大的把负的权值去掉代码块解释1.邻接表存图记录了每条边对应的所有边题目是无向图存的是双向边intn;cinn;for(inti1;in;i)cina[i];for(inti1;in;i){intu,v;cinuv;edges[u].push_back(v);edges[v].push_back(u);}2.深搜dpvoiddfs(intu,intfa){//当前节点和父节点dp[u]a[u];//初始化当前节点的美丽值为自己for(autoit:edges[u]){if(itfa)continue;//防止无向边走回头路死递归dfs(it,u);//递归调用计算it节点的值if(dp[it]0){//判断节点权值是否大于0dp[u]dp[it];//保留累加}}summax(dp[u],sum);//更新节点最优解}