题意：给定一颗无根树，每个点有一个点权，可以有负数。求一个联通块，使得这个联通块内的点权之和最大。

分析：我们看到这道题，第一反应是贪心。把每个点当做根跑一次贪心，在根的子树中，如果一个子树的权值和大于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
     
      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<