【P2014】选课（树状DP）

时间：2024-01-19 12:18:08

蒟蒻的第二道树形DP,话说看了这个题的正常做法之后一脸蒙，森林转二叉树？？什么诡异的操作，蒟蒻完全没明白那个原理是啥。。。可能是当初没好好学吧。。不管了，索性直接DP。

不难看出，这个题的DP方程和刚才那个大差不离，就是刚才那个题可以直接知晓应该留多少条边而这个需要计算一下罢了，考虑搜索中进行儿子数量的计算。。然后方程上略有一丝不同，一开始傻傻的把边权加进去，后来突然发现不对这个题给的是点权，于是就在前面把所有点都打进了DP数组，然后剩下的就没什么很大的不同了。

#include<iostream>

#include<cstdio>

#include<cstring>

#define re register

using namespace std;

int n,m,cnt=,head[],f[][],x,y,l,num,cost[];

struct tree

{

    int to,nxt,dis,from;

};

tree t[];

inline int read()

{

    int x=,c=;

    char ch=' ';

    while((ch<''||ch>'')&&ch!='-')ch=getchar();

    while(ch=='-')c*=-,ch=getchar();

    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

    return x*c;

}

inline void add_edge(int from,int to,int dis)

{

    t[++num].nxt=head[from];

    t[num].from=from;

    t[num].to=to;

    t[num].dis=dis;

    head[from]=num;

}

inline int solve(int from,int fa)

{

    int maxs=;

    for(re int i=head[from];i!=-;i=t[i].nxt)

    {

        int u=t[i].to;

        if(u==fa)

        continue;

        int s=solve(u,from);

        maxs+=s+;

        for(re int j=maxs;j>=;j--)

         for(re int k=;k<=s;k++)

             if(j-k->=)

            f[from][j]=max(f[from][j],f[from][j-k-]+f[u][k]);

    }

    return maxs;

}

int main()

{

    n=read();m=read();

    memset(head,-,sizeof(head));

    for(re int i=;i<=n;i++)

    {

        x=read();cost[i]=read();

        add_edge(i,x,cost[i]);

        add_edge(x,i,cost[i]);

    }

    for(re int i=;i<=n;i++)

    f[i][]=cost[i];

    solve(,);

    cout<<f[][m];

}

相关文章