自动搬运

查看原文

来自洛谷，原作者为

	Little_Jian **

搬运于2025-08-24 21:57:37，当前版本为作者最后更新于2019-08-01 14:43:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

个人博客链接

思路：

单独考虑每个点对答案的贡献，设 $d_i$ 表示 $i$ 到 $1$ 的距离，那么它产生的贡献就是 $k^{d_i}C_i$ 再加上环对答案的影响，所以 $R(1) = \frac{\sum_{i=1}^n k^{d_i}C_i}{1-k^{len}},len$ 为环长。 　　这样的话，不难发现每次修改肯定是把一个点连到 $1$ 的下面。 　　设 $dp[o][m][d]$ 表示在 $o$ 子树内当 $o$ 的深度为 $d$ 还有 $m$ 次修改机会时的最大可靠值。在树上的修改就是一个类似背包的 $\text{dp}$ 复杂度 $O(n^4)$。 　　但是如果对环做修改就会影响下面的分母。所以还要再枚举环长，每次重新 $\text{dp}$，所以复杂度就是 $O(n^5)$ 的。

代码：

#include <bits/stdc++.h>
#define File(_) freopen(#_ ".in", "r", stdin), freopen(#_ ".out", "w", stdout)
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 65;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int k) {return W[k];}
};
Link<N, N * 2, int> G;

int s[N];
db c[N], k;

db dp[N][N][N], tmp[N][N];
db pw[N];
void dfs(int o, int m, int dep) {
    rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = c[o] * pw[d];
    erep(k, G, o) {
        int v = G[k];
        dfs(v, m, dep + 1);
        mset(tmp, 0);
        rep(i, 0, m) rep(j, 0, m - i) rep(d, 0, dep) {
            tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j][d + 1]);
            if(j > 0) tomax(tmp[i + j][d], dp[o][i][d] + dp[v][j - 1][1]);
        }
        rep(i, 0, m) rep(d, 0, dep) dp[o][i][d] = tmp[i][d];
    }
}
db calc(int m) {
    dfs(1, m, 0);
    return dp[1][m][0];
}

int main() {
    File(trans);
    int n, m;
    scanf("%d%d%lf", &n, &m, &k);
    pw[0] = 1.0; rep(i, 1, n) pw[i] = pw[i - 1] * k;
    rep(i, 1, n) scanf("%d", &s[i]);
    rep(i, 1, n) scanf("%lf", &c[i]);
    db ans = 0;
    for(int d = 2, p = s[1]; p != 1; d++, p = s[p]) {
        G.clear();
        int t = s[p]; s[p] = 1;
        rep(i, 2, n) G.add(s[i], i);
        tomax(ans, calc(m - (t != s[p])) / (1 - pw[d]));
        s[p] = t;
    }
    printf("%.2lf\n", ans);
    return 0;
}