最大子树和

· · 题解

看到这道题，我的内心就告诉我，这是一篇树形dp 后来，仔细一看，

果然是！

刹那间，我惊了！！！

头脑中开始回忆 如何去把这个关系建立出来，终于我想到了，两种方法（这个人太蒟了吧），现在我来给大家讲一下啊！！！（不喜勿喷，毕竟博主太菜了）

我们先来说一下链式前向星存图，和邻接矩阵吧。

老师说，邻接矩阵是最好理解的了，（但垃圾啊）所以让我不要用， vector也可以，但是我好像不是很理解链表这一种数据结构，所以我也不会用

邻接矩阵：

其实就像他的字面义一样，就是一个二维数组的矩阵，用来存储两个点之间的所属关系，如果这两个点之间有联系，那么便在它们的二维矩阵的交点处附上1。所以说还是比较好理解了的。

但是呢，假如有五个点，那么就开一个5*5的二维矩阵，浪费的空间很多，所以我们又有了一个数据结构：链式前向星存图。

链式前向星：

若果有五个点，假设把他们想做是一个个的小房间，每个房间中藏有其他房间的钥匙，每个房间可以通往其他人的房间。现在我来讲一讲他的具体步骤吧：

有一个东西叫做st的里面存储的是第i条路的路径数。 所以呢，我们可以定一个结构体，具体代码如下：

struct Edge
{
        int nxt,to,val;
}e[6001];//这一步是定义一个结构体。
void add(int a,int b,int value)
{
        e[++tot].to = b;//拓展一个新的边
        e[tot].val = value;//这是这条边的权值
        e[tot].last = st[a];
        st[a] = tot;
}
//这是每一步都要做的事哦！
顺便附上遍历的代码：
for(int st[i];i != -1;i = e[i].last)
{

}
//这样我们就可以遍历全部的点了！！！：）

讲完了链式前向星存图，那么讲一下这题的思路了吧。

f[u]+=max(0,f[v]); (v为u的孩子) 有些儿子比较丑，美丽指数小于0，可能不选，所以与0作个比较

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
struct edge
{
    int next,to;
}e[100000];  
int n,a[100000],head[100000],h,f[100000],ans; 
void add(int x,int y) 
{
    e[++h].next=head[x];
    e[h].to=y;
    head[x]=h;
}
void dfs(int u,int fa)
{
    f[u]=a[u]; 
    for (int i=head[u];i;i=e[i].next) 
    {
        int v=e[i].to;  
        if (v!=fa)  
        {
            dfs(v,u);  
            f[u]+=max(0,f[v]);  
        }
    }
    ans=max(ans,f[u]); 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);//这里一定要维护双向边哦！
        add(y,x);  
    }
    dfs(1,0);  
    printf("%d",ans);
}

这个程序的状态转移是通过dfs来实现的，而树形dp的转移大多都可以通过dfs转移，所以说，这道题就这么结束了（逃