P5765 [CQOI2005] 珠宝 题解

· · 题解

双倍经验。

\large{\text{Solution}}

根据 P7393 的 结论，我们可以构造出 符合题意且最大点权为 k 的 节点最少的树。

发现当 k=11 的时候节点数最小的树的规模就远大于 5\cdot 10^4 了。因此这题只会出现点权为 [1,10] 的树（但是数据过水貌似只有到 4 的情况，显然可以构造出一组数据叉掉），于是可以直接写出 DP。

设 f_{u,i} 表示节点 u 取值为 i 的最小权值和，那么转移为

f_{u,i}=i+\min\limits_{v\in \operatorname{son}_u~,~j\ne i}\left(~f_{v,j}~\right)

\large{\text{Code}}

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> g[10010];
int f[10010][10];
void dp(int u,int fa){
    for(int i=1;i<=9;i++) f[u][i]=i;
    for(auto v:g[u]){
        if(v==fa) continue;
        dp(v,u);
        for(int i=1;i<=9;i++){
            int minn=1e9;
            for(int j=1;j<=9;j++){
                if(i==j) continue;
                minn=min(minn,f[v][j]);
            }
            f[u][i]+=minn;
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int aa,bb;
        cin>>aa>>bb;
        g[aa].push_back(bb);
        g[bb].push_back(aa);
    }
    dp(1,0);
    int ans=1e9;
    for(int i=1;i<=9;i++) ans=min(ans,f[1][i]);
    cout<<ans;
    return 0;
}

似乎很多人都觉得最大点权的上界是 \log_2n+1（甚至还有人证明了？），但其实做过 P7393 就会知道这个上界并非以那么简单的函数增长（貌似有人 oeis 都找不到那个序列），所以我们只能将其近似看做 \log_n。