P3177 [HAOI2015] 树上染色
很好的一道树形dp
具体哪些点选黑选白我们肯定是不知道的 但是题目最后要求的是求贡献
所以只要我们能算出贡献就好了
因为答案是线性的 简而言之就是 ∑每个边的贡献＝总贡献
考虑一条边的贡献
边一侧的黑节点数另一侧的黑节点数边权+一侧的白节点数另一侧的白节点数边权
设dp[u,i]表示u子树选i个黑点对总贡献的价值
初始状态：dp[u][0]=dp[u][1]=0;
转移方程：dp[u,k]=max(dp[u][k],dp[to][k-j]+val)
val = j(k-j)w + (sz[v]-j)(n-k+j-sz[v])w
w表示边权 sz[v]表示以v子树的节点数
点击查看代码
#include
#include
#include
using namespace std;
const int maxn = 2005;
struct Edge{
int x, y, w, nxt;
}e[maxn << 1 | 1];
int n, m, cnt;
int fr, to, haj;
int head[maxn], siz[maxn];
long long f[maxn][maxn];
inline int read(void)
{
int s = 0, w = 1;
char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') w = -1;
for(; ch <= '9' && ch >= '0'; ch = getchar()) s = s * 10 + ch - '0';
return s * w;
}
inline void add(int x, int y, int w)
{
e[++cnt].x = x;
e[cnt].y = y;
e[cnt].w = w;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs(int x, int father)
{
siz[x] = 1;
f[x][0] = f[x][1] = 0;
for(register int i = head[x]; i != -1; i = e[i].nxt)
{
int y = e[i].y;
if(y == father) continue;
dfs(y, x);
siz[x] += siz[y];
for(register int j = min(m, siz[x]); j >= 0; j--)
{
for(register int k = 0; k <= min(j, siz[y]); k++)
{
if(f[x][j - k] == -1) continue;
long long val = 1ll * e[i].w * k * (m - k) + 1ll * e[i].w * (siz[y] - k) * (n - m - siz[y] + k);
f[x][j] = max(f[x][j], f[x][j - k] + f[y][k] + val);
}
}
}
}
signed main()
{
memset(head, -1, sizeof(head));
memset(f, -1, sizeof(f));
n = read(); m = read();
for(register int i = 1; i < n; i++)
{
fr = read(); to = read(); haj = read();
add(fr, to, haj);
add(to, fr, haj);
}
dfs(1, 0);
cout << f[1][m] << '\n';
return 0;
}