P5765题解

· · 题解

感觉 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;
}