JZdalao昨天上课讲的题目，话说JSOI的题目是真的不难，ZJOI的题目真的是虐啊！

题意很简单，抽象一下就是：有一棵树，一次只能选从根到某个节点上的链上的所有点，问从中取出k个节点所得到的总价值和总代价的比最大是多少。

像这种比值最大的题目，很容易让人联想到分数规划

关于分数规划的姿势，可以自行百度

对于题意进行进一步分析，得到要求的是：

max{∑v[i]/∑w[i]}(if i is chosen)

因此我们设x，二分x，看看是否存在：

max{∑v[i]/∑w[i]}>=x(if i is chosen)

移项得每个点的权值c[i]：

c[i]=v[i]-x*w[i](1<=i<=n)

所以我们得出c[i]，然后看看能否在树上找出满足题意的点集使得点权和大于等于0

所以要找出最大值，再考虑树形DP

但是一般的背包DP和多叉树转二叉树DP都是O(n^3)的

所以可以用DFS序来完成这种树上的n个点选m个点的DP

具体如下：

1. 预处理出原树的DFS序，以及每个节点的子树大小

2. 进行DP 用f[i][j]表示DFS序列中前i-1个点中选取j个点中得到的最大点权和

3. 对于每一个f[i][j],可以转移：

• f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+c[s[i]]) （选这个点）

• f[i+size[s[i]]][j]=max(f[i+size[s[i]]][j],f[i][j]) （不选这个点,则直接跳过整棵子树）

最后判断f[n+1][k]是否大于等于0

注意这里的人数不包括根节点，因此k要加1

CODE

// luogu-judger-enable-o2

#include<cstdio>

#include<cstring>

using namespace std;

typedef double DB;

const int N=2505;

const DB EPS=1e-5,INF=1e9;

struct edge

{

    int to,next;

}e[N];

int head[N],v[N],w[N],size[N],s[N],n,k,x,cnt,tot;

DB f[N][N],c[N];

inline char tc(void)

{

    static char fl[100000],*A=fl,*B=fl;

    return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

    x=0; char ch=tc();

    while (ch<'0'||ch>'9') ch=tc();

    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();

}

inline void add(int x,int y)

{

    e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;

}

inline void DFS(int now)

{

    s[++tot]=now; size[now]=1;

    for (register int i=head[now];i!=-1;i=e[i].next)

    DFS(e[i].to),size[now]+=size[e[i].to];

}

inline DB max(DB a,DB b)

{

    return a>b?a:b;

}

inline bool check(DB x)

{

    register int i,j;

    for (i=1;i<=n;++i)

    c[i]=(DB)v[i]-(DB)x*w[i];

    for (i=1;i<=tot+1;++i)

    for (j=0;j<=k;++j)

    f[i][j]=-INF;

    for (f[1][0]=0,i=1;i<=tot;++i)

    for (j=0;j<=k;++j)

    {

        f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+c[s[i]]);

        f[i+size[s[i]]][j]=max(f[i+size[s[i]]][j],f[i][j]);

    }

    return f[tot+1][k]>=0;

}

int main()

{

    register int i;

    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

    memset(e,-1,sizeof(e));

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

    read(k); read(n); ++k;

    for (i=1;i<=n;++i)

    {

        read(w[i]); read(v[i]); read(x);

        add(x,i);

    }

    DFS(0);

    DB l=0,r=1e4;

    while (r-l>EPS)

    {

        DB mid=(DB)(l+r)/2;

        if (check(mid)) l=mid; else r=mid;

    }

    printf("%.3lf",l);

    return 0;

}