典型的树形DP,但是做起来还是要看题解,看来还是不会吖.

题目背景

小$A$在果园里发现了一棵结满果子的树，于是他就打起了坏主意，他打算把树的一部分砍下来带回家。

题目描述

我们可以把这棵树表示成一个树型的结构，也就是说，任意两个点之间有且仅有一条路径。在每个点$i$处都结着一个水果，每个水果有一个价值$v_i$和重量$w_i$。小$A$想带走树的一部分（或全部），包含至少$K$个结点（也就是至少$K$个水果），且这些水果的平均价值尽可能高。平均价值是指水果总的价值除以总的重量。注意小$A$砍下的树必须是在原来的树中连通的一部分。

输入格式

第一行包含两个数$N$和$K$，分别表示树的结点数和小$A$至少应带走的水果数。第二行包含空格隔开的$N$个数，分别表示每个结点处水果的价值$v_i$。第三行包含空格隔开的$N$个数，分别表示每个水果的重量$w_i$。按下来$N-1$行，每行包含两个数$a_i$和$b_i$ （$1 ≤ a_i, b_i ≤ N$），表示在结点$a_i$和$b_i$之间有一条边。输入保证是一棵正确的树结构。

输出格式

输出一行，包含一个数，表示最大可能的平均价值。四舍五入到小数点后两位。

数据范围

对$100%$的数据，$1 ≤ N ≤ 100, 1 ≤ K ≤ N, 1 ≤ v_i ≤ 10000, 1 ≤ w_i ≤ 10000$

解析

看到价值和重量,就知道这是一道我不会的树上背包问题.一般背包可以设$f_{i}$表示选择重量不超过$j$的物品能获得的最大价值,但是这道题要结合树形结构,而且$w$和$v$的范围都很大,所以考虑基于个数来设置状态.

我们设$f_{i,j}$表示在以$i$为根的子树中选择$j$个点能获得的最大平均价值.对于它的每棵子树,我们枚举从中选择了多少节点来转移.

※因为题目要求记录平均值,而平均值并不容易直接转移,所以我们将$f$数组开成结构体,记录当前状态的总重量,总价值,以及平均值(总价值/总重量).这道题显然是树上$01$背包,因此别忘了要倒序循环外层.

struct node {
    double w, v, ave;//重量,权值,平均值
    node() {}
    node(double a, double b, double c) : w(a), v(b), ave(c) {}
}f[105][105];

void dfs(int now, int father) {
    f[now][1] = node(w[now], v[now], v[now] / w[now]);//为了维护连通性,根节点肯定要选.
    for (int i = head[now]; i; i = nxt[i]) {
        if (to[i] == father)//枚举每个子节点
            continue;
        dfs(to[i], now);//先递归下去,再由叶到根更新
        for (int j = n; j > 1; --j) {//枚举以now为根的子树中一共选择多少个点,注意01背包要倒序
            for (int k = 1; k <= j; ++k) {//枚举当前子树中选择了j个节点中的多少个
                node p = f[to[i]][j - k];//在这个子树中选择了j个节点中的j-k个点
                node q = f[now][k];//在其他子树中选择了k个点.
                double ave = (p.v + q.v) / (p.w + q.w);//计算平均值
                if (ave >= f[now][j].ave) {//更新答案
                    f[now][j] = node(p.w + q.w, p.v + q.v, ave);
                }
            }
        }
    }
    return;
}

最后在所有$f[i][j](k \le j \le n)$中选择最大值输出即可.

感觉还是不会呢

——Gensokyo