洛谷P4395 [BOI2003]Gem 气垫车 题解

题目链接：P4395 [BOI2003]Gem 气垫车

题意：给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数

唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。

$N \le 10000$

考虑树形dp

设 $dp[u][i]$ 表示结点 $u$ 的权值为 $i$ 时其所在子树的最小总权值

则有

$$dp[u][i]=\min_{k \ne i}(dp[v][k])+i$$

那么这个权值最大有多少呢

不难发现最多为 $\left\lceil\log n\right\rceil + 1$

那么就很简单了，时间复杂度 $O(n\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
#define N (int)(2e4+15)

struct Edge
{
    int u,v,next;
}e[N];
int n,pos=1,dp[N][17],head[N];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int f)
{
    for(int i=1; i<=15; i++)
        dp[u][i]=i;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u);
        for(int j=1; j<=15; j++)
        {
            int mn=INF;
            for(int k=1; k<=15; k++)
                if(j!=k)mn=min(mn,dp[v][k]);
            dp[u][j]+=mn;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v);
        addEdge(v,u);
    }
    dfs(1,0);
    int res=INF;
    for(int i=1; i<=15; i++)
        res=min(res,dp[1][i]);
    cout << res << endl;
    return 0;
}