自动搬运

查看原文

来自洛谷，原作者为

	CNCAGN 他们说的退役太沉重 你在路上追着你的梦 前路会与过往不同 但精彩纷呈

搬运于2025-08-24 22:14:10，当前版本为作者最后更新于2023-10-11 08:42:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉 P5765 和 P4395 都没有对于最大点权太认真的证明，故写了此题解。第一次自己证明这种结论如有纰漏或错误欢迎指出。

题目描述

题目给出一个树的边，要求自选正整数点权值（即填色），使得点权和最小，同时要求相邻的两个点的点权不等。

Solution

树形动规的绿题一般比较相似，这个题就和上司的舞会很像。

动规方程也很好推，令 $f_{u,i}$ 代表 $u$ 为根的树，点权为 $i$ 的情况下权值和的最小值。

则 $f_{u,i}=i+\sum\min(f_{v,j}) \ (j{\neq}i,v{\in}son_u)$。

考虑用 $1$ 和 $2$ 来填色，思路很快就假，如下图所示，$1,2,3$ 填色明显比 $1,2$ 填色更优。

讨论区也有说最大用 $1,2,3,4$ 即可满足最小填色，也可通过上图规模的扩大进行否定。

考虑正解，对于本题任意一颗树的填色方案，总有一个最大的点权。那么 dp 的前置问题转化为：一个 $n$ 个点的树按本题规则填色，最大点权为何。

我比较菜直接想不出来，但是可以把这个问题转化：已经填好树上点权且最优，若这个点的点权为 $x_i$，那么求这个点的子树最小有多少个点（设为 $num_i$）。据此，若有一点权为 $x$ 的点，使得 $num_i{\ge}n$，则这颗 $n$ 点的子树一定可以用 $1,2,3,\cdots,x_{i-1},x_i$ 来获得总权值最小的填色。

若最优答案树上一个点的点权为 $x$，那么显然这个点一定连接点权为 $1$ 到 $x-1$ 的所有的点，那么简单的打个表找规律（下图带颜色的数字代表点的个数）：

发现最大点权 $x_i$ 的最优最小子树的 $num_i$ 为 $2^{x_i-1}$。所以题目 $n$ 个点的树最大用 $\log_2n+1$ 即可最优填色，对于此题为 $16$ 左右，完全可过。至此，这个题最关键的步骤结束了。代码可能是最简单的部分了。简单 dfs 和 dp 即可。

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<map>
using namespace std;
inline int red() {
    int op = 1, x = 0;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-')   op = -1; 
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return op * x;
}
const int maxn = 1e5 + 10, maxm = 1e5 + 10, maxx = 16;
const int inf = 0x3f3f3f3f;
int n, x;
int root;
int deg[maxn];
int f[maxn][maxx];
int head[maxn], to[maxm], nxt[maxm];
int num;
void add(int a, int b) {
	to[++num] = b;
	nxt[num] = head[a];
	head[a] = num;
}
void dfs(int u, int fa) {
	for(int i = 1; i <= x; ++i) {
		f[u][i] = i;
	}
	for(int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == fa)	continue;
		dfs(v, u);
		for(int j = 1; j <= x; ++j) {
			int minn = inf;
			for(int k = 1; k <= x; ++k) {
				if(k == j)	continue;
				minn = min(minn, f[v][k]);
			}
			f[u][j] += minn;
		}
	}
}
int main() {
	n = red();
	x = log(n) / log(2);
	++x;
	for(int i = 1; i < n; ++i) {
		int a = red(), b = red();
		add(a, b);
		add(b, a);
		++deg[a], ++deg[b];
	}
	root = 1;
	dfs(root, -1);
	int ans = inf;
	for(int i = 1; i <= x; ++i) {
		ans = min(ans, f[1][i]);
	}
	printf("%d\n", ans);
    return 0;
}