题解 P1352 【没有上司的舞会】

邻接矩阵存图~

对于一个点，令d（i，j）表示他去或不去，所有子树的和；

那么，只需要依次加上所有点，即可完成状态转移。

另外，记忆话搜索需要从根开始。

所以需要搜一遍，找到校长。

上代码；

#include<stdio.h>
#include<algorithm>
using namespace std;
int n;bool map[6000][6000];
int val[6000];int d[6000][2];
int mdfs(int x,int jud)//记忆话搜索
{
    if(d[x][jud]!=-1)
    {
        return d[x][jud];
    }
    if(jud==0)//不去
    {
        d[x][jud]=0;//消掉-1的标记
        for(int i=0;i<n;i++)
        {
            if(map[x][i])//查找邻接矩阵
            d[x][jud]+=max(mdfs(i,0),mdfs(i,1));//子树和
        }
    }
    else if(jud==1)//去
    {
        d[x][jud]=val[x];//加上权值
        for(int i=0;i<n;i++)
        {
            if(map[x][i])
            d[x][jud]+=mdfs(i,0);//下属只能不去
        }
    }
    //printf("mdfs %d %d=%d\n",x,jud,d[x][jud]);调试语句
    return d[x][jud];
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)//手动memset~
    {
        for(int j=0;j<2;j++)
        {
            d[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&val[i]);
    }
    for(int i=0;i<n-1;i++)
    {
        int u;int v;
        scanf("%d%d",&u,&v);
        map[v-1][u-1]=true;
    }
    int start=0;
    for(int i=0;i<n;i++)//搜一遍图，找校长
    {
        for(int j=0;j<n;j++)
        {
            if(map[j][i])goto skip;
        }
        start=i;break;
        skip:;
    }
    int res=max(mdfs(start,0),mdfs(start,1));//校长去与不去
    printf("%d",res);
    return 0;//拜拜程序
}