不建树大法师（dfs)

· · 题解

先给代码-.-

#include<iostream>
#include<cstdio>
using namespace std;
bool f[16002][16002]={false};
int w[16002][2]={0},i,a,b,o=0,n;

int sum(int a){
    int j;
    if(w[a][2]==0){
        if(w[a][1]<0)return 0;
        else return w[a][1];
    }
    for(j=3;j<=n+2;j++)if(f[a][j]){
        f[a][j]=false;f[j-2][a+2]=false;
    w[a][1]=w[a][1]+sum(j-2);
    if(w[a][1]>o)o=w[a][1];
    }

    if(w[a][1]<0)return 0;
        else return w[a][1];
}

int main ()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i][1]);
}
for(i=1;i<=n-1;i++)
{
    scanf("%d%d",&a,&b);
    w[a][2]++;
    w[b][2]++;
    f[b][a+2]=true;
    f[a][b+2]=true;
}
sum(1);
printf("%d",o);
return 0;

}

随便确定随便一个点开始(最后证明为什么这样可以)，代码里面从1开始的。（就是sum（1））

W[1][1]是第一个点的值，W[1][2]是和这个点连接的数量，后面是记录和这个点连接的点。

f数组是记录两个点是否连接。f[x][y]是x点是否能到y点，如果x能到y点那么y点也能到x点，所以f[y][x]也是打开的。

然后就开始深搜。深搜的时候要记得把f关闭，不然会死循环！！！而且双向路都要关闭！！！

搜到最底下就把这个点的值递回来，然后加上沿路所有点的值。

！！！！！最重要的一点，如果这个值小于0那么返回0！！！！！ ！！！！！因为如果值小于0那么还不如不要这个点！！！！！！！

开始证明为什么从任意一个点开始都行，就拿样例来证明啦

这是把1当做根构造的树，深搜到底发现最下面的值是-1，所以就返回0，然后1+0=1，5和6还是1，然后继续返回0+1+1=2，所以7的值变成2，然后2+1=3，所以4的值是3.最后发现1的值-1小于0，那么就把1的值变成0，然后0+3=3。最终答案3

这是把7当做根的树，深搜到最底下发现1,2,3点的值都是-1，因为-1<0所以返回0。4,5,6点的值是0+1=1。然后继续返回值，点7的值是0+1+1+1=3，所以最终答案是3

由此发现无论从哪个点开始都可以算出正确答案，可以证明我们的思路是正确的。

最后说一句

DP的题真是练习搜索的好题呢！！！！

第一篇题解，蒟蒻求过QWQ

O(∩_∩)O谢谢