一道水题，我也不知道为什么要写博客，这应该是最后一次了

\(Description\)

给你\(n\)个节点的树，要求你在上面选取一个联通块，使得点权和最大

\(Soution\)

树形\(DP\)，我们实际上是在求一颗子树，用\(dp[i]\)表示以\(i\)为根的子树能得到的最大值即可 转移方程显然：\(DP[i]=a[i]+\Sigma_j max(DP[j],0)\)其中\(j\)为\(i\)的子节点 初始化在上诉方程中表示了，就是初始化为点权即可

\(Code\)

#include<cstdio> #include<iostream> #define re register #define maxn 160100 using namespace std; int n,a[maxn],x,y,cnt,head[maxn],ans,dp[maxn]; struct Edge{ int v,nxt; }e[maxn<<2]; inline void add(int u,int v) { e[++cnt].v=v; e[cnt].nxt=head[u]; head[u]=cnt; } void dfs(int now,int fa) { dp[now]=a[now]; for(int i=head[now];i;i=e[i].nxt) { int ev=e[i].v; if(ev==fa) continue; dfs(ev,now); dp[now]+=max(0,dp[ev]); } ans=max(ans,dp[now]); } int main() { scanf("%d",&n); for(re int i=1;i<=n;++i) scanf("%d",&a[i]); for(re int i=1;i<n;++i) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,0); printf("%d",ans); return 0; }

转载于:https://www.cnblogs.com/Liuz8848/p/11284594.html