题解：CF1211H Road Repair in Treeland

· · 题解

UPD：代码被 Ryanhao hack 了，已经修复。

没有调过去的同学可以看看这组 hack。

hack 数据：

1
9
1 2
1 3
2 4
2 5
2 6
3 7
3 8
3 9

答案是 2。

这道题评黑的原因是不是因为不会 Kotlin 语言导致的啊……

看到这种“最小的最大”/“最大的最小”，很容易想到二分答案。

所以第一步很明确：先二分答案。

那么我们一看，答案的上界显然是 n，那么二分答案这部分复杂度 O(\log(n))。

然而，n 只有 3000。于是肯定是 O(n^2\log n) 了。

然后我们发现这个东西很能 dp。具体的，考虑 f_{u,j} 表示目前 dp 到节点 u，满足目前选的所有数字的个数都 \le 二分的值 mid，设 u\to fa_u 这条边的颜色为 col，u 子树内（包含 u\to fa_u 这条边）的颜色等于 col 的边的数量为 j，不等于 col 的数量的最小值。

转移十分显然。只需要分 u\to v 和 col 的关系即可。下面是转移式子：

1. 若 u\to v=col

f_{u,j+k}=\min_{f_{v,k}\le mid}\{f'_{u,j}\}

2. 若 u\to v\neq col

f_{u,j}=\min_{f'_{u,j}+k\le mid,f_{v,k}\le mid}\{f'_{u,j}+k\}

容易发现这个东西是 O(n^2) 的。

再加上二分，一共是 O(n^2 \log n) 的。

输出方案是容易的。

代码（并没有使用 Kotlin 语言实现，用的是 C++17，加入了格式化）：


#include <bits/stdc++.h>
using namespace std;
const int N = 3000 + 7, INF = 1e8;
bool __st;
double Time()
{
    return 1. * clock() / CLOCKS_PER_SEC;
}
void cmin(int &a, int b)
{
    if (a > b)
        a = b;
}
int sz[N], n, dp[N][N], MX, f[N];
vector<int> G[N];
void init()
{
    for (int i = 0; i <= (n); ++i)
        for (int j = 0; j <= (n); ++j)
            dp[i][j] = INF;
}
int dep[N];
pair<int, int> edge[N];
void dfs(int u, int fa)
{
    dp[u][(u != 1)] = 0;
    sz[u] = 1;
    for (int v : G[u])
    {
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        for (int i = 0; i <= (sz[u] + sz[v]); ++i)
            f[i] = INF;
        for (int now = 0; now <= (sz[u]); ++now)
            for (int chs = 1; chs <= (sz[v]); ++chs)
            {
                if (dp[v][chs] > MX)
                    continue;
                if (now > MX)
                    continue;

                //We color it with the same to fa
                if (now + chs <= MX)
                {
                    cmin(f[now + chs], dp[u][now]);
                }
                {
                    //color it with diff color with fa

                    if (dp[u][now] + chs <= MX)
                        cmin(f[now], dp[u][now] + chs);
                }
            }
        sz[u] += sz[v];
        for (int i = 0; i <= (sz[u]); ++i)
            dp[u][i] = f[i];
    }
}
bool check(int x)
{
    init();
    MX = x;
    dfs(1, 1);
    for (int j = 0; j <= (x); ++j)
    {
        if (dp[1][j] <= x)
            return 1;
    }
    return 0;
}
int col[N][2];
int tot = 0;
bool edgecol[N][N];
int laskid[N], FA[N];
pair<int, pair<int, int>> state[N][N];
void dfs2(int u, int fa)
{
    dp[u][(u != 1)] = 0;
    sz[u] = 1;
    FA[u] = fa;
    int las = 0;
    for (int v : G[u])
    {
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs2(v, u);
        for (int i = 0; i <= (sz[u] + sz[v]); ++i)
            f[i] = INF;
        for (int now = 0; now <= (sz[u]); ++now)
            for (int chs = 1; chs <= (sz[v]); ++chs)
            {
                if (dp[v][chs] > MX)
                    continue;
                if (now > MX)
                    continue;

                //We color it with the same to fa
                if (now + chs <= MX)
                {
                    if (dp[u][now] < f[now + chs])
                    {
                        cmin(f[now + chs], dp[u][now]);
                        state[v][now + chs] = make_pair(las, make_pair(now, chs));
                        edgecol[v][now + chs] = 1;
                    }
                }
                {
                    //color it with diff color from fa
                    if (dp[u][now] + chs <= MX && dp[u][now] + chs < f[now])
                    {
                        cmin(f[now], dp[u][now] + chs);
                        state[v][now] = make_pair(las, make_pair(now, chs));
                        edgecol[v][now] = 0;
                    }
                }
            }
        sz[u] += sz[v];
        for (int i = 0; i <= (sz[u]); ++i)
            dp[u][i] = f[i];
        las = v;
    }
    laskid[u] = las;
}
int Ans[N];
void Go(int u, int j, int fcol)
{
    /*
    Go(u,j,fcol)是我到了节点u，fa->我时fa的状态是j，fa->我的颜色为fcol
    */
    if (!u)
        return;
    col[u][1] = fcol;
    col[u][0] = ++tot;
    Ans[u] = fcol;
    if (u != 1)
    {
        int nxt = state[u][j].first, nxtj = state[u][j].second.first;
        Go(nxt, nxtj,
           col[FA[u]][edgecol[nxt][nxtj]]);
    }
    if (!laskid[u])
        return;
    int vv = laskid[u];
    Go(vv, (u == 1 ? j : state[u][j].second.second), col[u][edgecol[vv][(u == 1 ? j : state[u][j].second.second)]]);
}
void work(int x)
{
    init();
    MX = x;
    tot = 0;
    for (int i = 0; i <= (n); ++i)
        for (int j = 0; j <= (n); ++j)
            state[i][j] = {0, make_pair(0, 0)}, edgecol[i][j] = 0;
    dfs2(1, 1);
    for (int j = 0; j <= (x); ++j)
    {
        if (dp[1][j] > x)
            continue;
        Go(1, j, tot = 1);
        return;
    }
}
int solve()
{
    cin >> n;
    for (int i = 1; i <= (n); ++i)
        G[i].clear();
    int l = 1, r = n, ans = -1;
    for (int i = 1; i <= (n - 1); ++i)
    {
        int u, v;
        cin >> u >> v;
        edge[i] = make_pair(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ans << "\n";
    work(ans);
    for (int i = 1; i <= (n - 1); ++i)
    {
        auto [u, v] = edge[i];
        if (dep[u] > dep[v])
            swap(u, v);
        cout << Ans[v] << ' ';
    }
    cout << '\n';
    return 0;
}
main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

模拟赛切了，感觉不是很难。至少没有到黑的难度。比较倾向于蓝题。