2025/2/7课堂记录

目录

• 二叉苹果树
  
• 选课
  

• 二叉苹果树
  

这是一道树上依赖背包题，也叫做分组背包
依赖：选这一个，从它到根所有节点都要选，具有依赖性
分组：每个节点下的子节点分好几个组，每一个组单独做背包
maketree：因为题目没告诉父子关系，要自己推
看注释！！就写了亿点点注释[code] #include#includeusing namespace std;int map[110][110],l[110],r[110],ap[110],f[110][110];int n,q;void maketree(int a){        for(int i=1;i=0)//找到啦（你的破绽，砰！                 {                        l[a]=i;//标记左孩子（其实也不一定，但无所谓                         ap=map[a];//所有的苹果放在孩子身上，这步是关键思想！！！！！！！！！                         map[a]=-1;//删边                         map[a]=-1;                        maketree(i);//从孩子接着往下推                         break;//一定要炸掉，不然l[a]就被顶替了                 }        for(int i=1;i=0)                {                        r[a]=i;                        ap=map[a];                        map[a]=-1;                        map[a]=-1;                        maketree(i);                        break;                }}int dp(int fa,int num)//dp(fa,num)和f[fa][num]的含义都是fa节点必选，总共选num个节点最多苹果数 {        if(num==0)return 0;//一个都没有那就一个都没有呗         if(l[fa]==0)return ap[fa];//没有孩子那就只有自己呗（此时num肯定>0）         if(f[fa][num]>0)return f[fa][num];//之前来过了，不用再来了         for(int i=0;i>n>>q;//n:节点数量，q：保留边数量         q++;//保留q条边，实际就是保留q+1个节点（父亲+每一条边后面跟着一个节点         memset(map,-1,sizeof(map));//初始化负数         for(int i=1;i>x>>y>>z;                map[x][y]=z;//因为输入的时候父亲孩子没有固定顺序                 map[y][x]=z;//所以双向建图就行，反正用的链接表，多余空间不用白不用         }        maketree(1);//从根节点一点一点往下推         cout=1;t--)                {                    f[t]=f[t-1]+a;                        }         }}int main(){    cin>>m>>n;    //这里并没有把树根单独拎出来的原因是把所有树根直接绑在了0上，相当于0是根，所有的“根”都是0的孩子        //把一片树林看作一颗树     for(int i=1;i>x>>y;        a=y;                //存储成有向图的方式         tr[x].push_back(i);  //x是父亲，i是孩子     }    dfs(0);//森林的根     cout