年会 （C语言代码）------------------------C语言——菜鸟级

解题思路:

 记忆化搜索 + 二叉树

常理来说大学里 一个导师可以有多个学员 但一个学员只能有一个导师（二叉树）

 导师和学员不能同时邀请，那就是除了同时邀请外 还有三种情况，邀导不邀学

邀学不邀导 和都不邀 （0与1 ）的关系 通过DFS枚举各类情况，优化记忆数组；

       原文       欢迎访问我的博客
注意事项:

参考代码: 

#include <string.h>
#include <stdio.h>
#define M 6002
#define max(a,b) a>b?a:b
int n;
int v[M]; 
int bj[M];
//标记非根节点（将有学员身份的员工或者学员标记）
//没标记的就只有导师身份（即根节点） 
int ds[M][5001];
//导师数组 ds[i][j]=4；代表第i个人作为导师身份时第j个学员为4号学员 
int dp[M][2];//记忆数组 dp[L][0]代表满足条件下不邀请该员工（L）的最优活跃度
             // dp[L][1]代表满足条件下邀请该员工(L)的最优活跃度
int dfs(int L,int last)
{   //优化 记忆数组 
    if(last==1&&dp[L][0]!=-1)return dp[L][0];
    if(last==0&&dp[L][1]!=-1)return dp[L][1];
if(!ds[L][0])//表示 当前员工无学员 即 该员工只有学员身份 
{ if(last==0&&v[L]>0)return v[L];//若该员工的导师未邀请且该学员可i活跃气氛 
 else return 0;//不活跃当然不能要； 
}
    int ans1=0, ans2=0,i;
   //若不邀请该员工 就去找该员工的学员（下一层节点）的最优解 
    i=0;while(ds[L][i]!=0)ans1+=dfs(ds[L][i],0),i++;
     //若该员工的导师没被邀请 并且邀请该员工 然后去找该员工的学员（下一层节点）的最优解 
if(last!=1)i=0;while(ds[L][i]!=0)ans2+=dfs(ds[L][i],1),i++;
        
       if(last==0)//若该员工的导师未邀请  
{dp[L][1]=max(ans1,ans2+v[L]);
//该节点的最优解为（邀请该员工 与不邀请的该员工的）最大值 
//（即可能 该员工和他导师活跃值为负 都不邀请滴好） 
 return dp[L][1];
}//若该员工的导师邀请 ，那该员工只能不邀请 
 dp[L][0]=ans1;
 return dp[L][0];
}
int main()
{ int i,l,k,j,ans=0;
     scanf("%d",&n);
    memset(bj,0, sizeof(bj));
    memset(ds,0, sizeof(ds)); 
    memset(dp,-1,sizeof(dp));
    for(i=1;i<=n;i++)
    scanf("%d",&v[i]);
    while(1)
       {    
         scanf("%d%d",&l,&k);
        if(l==0&&k==0)break;
        j=0;
        while(ds[k][j]!=0)j++;//给l学员在他导师那找个序号位置 
                ds[k][j]=l;
        bj[l]=1;//标记该员工有学员身份 
    }
    for(i=1;i<=n;i++)//枚举根节点（ 只有导师身份的人） 
    if(!bj[i])ans+=dfs(i,0);//把各各没有关系的导师集合的最优解加起来 
    printf("%d\n",ans);
    return 0;
}