题解：P8916 [DMOI-R2] 暗号

AC_Lover · 2025-10-24 08:44:54 · 题解

P8916 [DMOI-R2] 暗号

体现了一种费用提前计算的思想。明显考虑 \mathrm{dp}，计算需要用到【子树中同色点权值和】状物，直接放进 \mathrm{dp} 状态里由于权值和太大状态数很多，并且转移需要背包，非常劣。考虑拆贡献思想，与其对计算每个点计算其子树中点的贡献和，我们转而计算每个点会被贡献多少，不难发现对于点 u，其贡献次数为到根的链上同颜色相邻点对个数，如果我们将这个放进状态里，每个点的贡献可以快速计算为 w_u\times cnt。于是考虑定义 f_{u,i,j,0/1} 表示考虑 u 子树内的所有点，到根的 0/1 同颜色相邻点对个数分别为 i,j，且当前点染成 0/1 时，子树内所有点贡献和的最大值。转移是简单的，从儿子转移过来时若同色则贡献到 i/j 即可：

最后需要算上当前点 u 的贡献，这是简单的：

时间复杂度 O(n^3)，可以通过。

:::info[代码]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T>void Max(T &x,T y) { if (y>x) x=y; }
const int N=310;
int n;
int h[N],e[N<<1],ne[N<<1],idx;
void add(int u,int v) { e[idx]=v,ne[idx]=h[u],h[u]=idx++; }
int w[N];
int dep[N];
ll f[N][N][N][2];

void dfs(int u,int fat)
{
    dep[u]=dep[fat]+1;
    for (int _=h[u];_!=-1;_=ne[_])
    {
        int v=e[_]; if (v==fat) continue; dfs(v,u);
        for (int i=0;i<=dep[u];i++)
        {
            for (int j=0;i+j<=dep[u];j++)
            {
                f[u][i][j][0]+=max(f[v][i][j][1],f[v][i+1][j][0]);
                f[u][i][j][1]+=max(f[v][i][j][0],f[v][i][j+1][1]);
            }
        }
    }
    for (int i=0;i<=dep[u];i++)
    {
        for (int j=0;i+j<=dep[u];j++)
        {
            f[u][i][j][0]+=1ll*(i+1)*w[u];
            f[u][i][j][1]+=1ll*(j+1)*w[u];
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin >> n;
    memset(h,-1,sizeof(h));
    for (int i=1;i<n;i++)
    {
        int u,v; cin >> u >> v;
        add(u,v), add(v,u);
    }
    for (int i=1;i<=n;i++) cin >> w[i];

    dep[0]=-1; dfs(1,0);
    cout << max(f[1][0][0][0],f[1][0][0][1]) << "\n";

    return 0;
}

:::