题意：给定一颗无根树，每个点有一个点权，可以有负数。求一个联通块，使得这个联通块内的点权之和最大。
分析：我们看到这道题，第一反应是贪心。把每个点当做根跑一次贪心，在根的子树中，如果一个子树的权值和大于0，就把子树的权值加上，否则就剪去这个子树。这样从根节点一层一层递归下来，先处理点的子树，再处理点本身，我们就得到了以某个节点为根的最大权值和。每个点都跑一次，取一个最大值，就得到了答案。这样做一定是对的，但是复杂度O(n^2)，加一个记忆化搜索能过。
但今天要讲的是Tree DP的思路。随便选一个点作为根，记f[i]为以i为根的子树的最大权值和，跑一次树上的DP就行。虽然有递归，但每个点只会经过一次，复杂度O（n）。
至于为什么以任意一个点作为根都行，请看下面的分析：
假设我们以节点1为根算出了一个最大联通块和，此时的联通块中一定包含节点1的权值。如果以2为根算最大权值，那分为两种情况：如果没有节点2这一部分，f[1]都大于0的话，那么节点2做DP时一定会把1那部分加上，结果就等效为从节点1做DP。如果没有节点2这一部分，f[1]小于0的话，说明节点1的权值小于0，那么2肯定不会选1这部分，程序中很重要的一句ans=max(ans,f[u]);就发挥了作用，它记录了以2为根的子树的答案，相当于以2为根不选1那部分的答案，还是等效的。所以，以2为根的话，无论哪种情况，都是和以1为根的情况是等效的，其他点同理。所以，我们只要任选一个点为根就可以了。
#include<bits/stdc++.h> using namespace std; int n,ans,ecnt; int a[16005]; bool vis[16005]; int head[16005]; int f[16005]; struct aaa { int to,nxt; }bian[32100]; inline int read() { int x=0;bool f=0;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();} return f?-x:x; } inline void add(int a,int b) { bian[++ecnt].to=b; bian[ecnt].nxt=head[a]; head[a]=ecnt; } void dfs(int u) { vis[u]=1;f[u]=a[u]; for(int i=head[u];i;i=bian[i].nxt) { int v=bian[i].to; if(!vis[v]) { dfs(v); f[u]+=max(0,f[v]); } } ans=max(ans,f[u]); } int main() { n=read(); int aa,bb; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n-1;i++) { aa=read();bb=read(); add(aa,bb);add(bb,aa); } dfs(1); cout<<ans; return 0; }
原文：https://www.cnblogs.com/oierjzy/p/11260140.html