20260731

P4395 [BalticOI 2003] Gem 气垫车 (Day 1)

思路

树形dp。

不难发现权值只染 \(1\) 和 \(2\) 是假的，只能获得 \(18\) 分。

观察可得权值最多有 \(\log n\) 种，所以设 \(dp[i][j]\) 为第 \(i\) 个节点权值为 \(j\) 时以 \(i\) 为根的最小的权值之和。

则枚举 \(i\) 的子节点 \(k\)，权值 \(p\)，有 \(dp[i][j] += min(dp[k][p])(p != i)\)

点击查看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, dp[N][20];
vector<int> g[N];
void dfs(int u, int fa)
{for(int i = 1; i < 20; i ++) dp[u][i] = i;for(int v : g[u]){if(v == fa) continue;dfs(v, u);int minn = 1e9;for(int i = 1; i < 20; i ++){minn = 1e9;for(int j = 1; j < 20; j ++){if(i == j) continue;minn = min(minn, dp[v][j]);}dp[u][i] += minn;}}
}
signed main()
{cin >> n;for(int i = 1; i < n; i ++){int x, y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}dfs(1, -1);int ans = 1e9;for(int i = 1; i < 20; i ++) ans = min(ans, dp[1][i]);cout << ans << endl;
}

双倍经验：P5765 [CQOI2005] 珠宝