CF 1795F Blocking Chips

標籤： cf

给定一个树。有 $k$ 个 chip，分别位于 $a_0, a_1, a_2, \cdots, a_{k-1}$，且互不相同，在时间 $i$ 第 $i \bmod k$ 个 chip 要移动到一个没有被任何 chip 到达过的地方，问在何时某个 chip 无法移动。

首先二分答案，这样我们就可以求出每个 chip 需要移动的步数。

贪心，对于每个节点，尽量让其在子树内完成所需步数。令 $f_i$ 表示可以从 $i$ 节点往子树下走的步数，同时当 $f_i < 0$ 时表示 $i$ 节点需要往上走的步数（的相反数）。

对于节点 $i$，如果儿子中存在有两个都要向上走，或本身就是 chip 出发点且有一个儿子要向上走，则无解。如果有一个要向上走的，则优先走到其他儿子处，若所有儿子均不能满足，则向上走。

下面代码中，graph::check() 使用于判断答案是否可行的函数。

struct graph
{
    vector<vector<int>> e;
    vector<int> a;
    int k;
    graph(int n) : e(n), a(n, -1) {}
    void add_edge(int u, int v)
    {
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
 
    bool dfs(int u, int from, const vector<int> &len, vector<int> &f)
    {
        // need 表示到 u 出发需要走的长度，maxf 表示儿子中最大的 f
        int need = -1, maxf = 0;
        if (a[u] > -1) {
            need = len[a[u]];
        }
        for (auto v : e[u]) {
            if (v == from) continue;
            bool flag = dfs(v, u, len, f);
            if (!flag) return false;
            if (f[v] < 0) {
                if (need > -1) return false;
                need = -f[v] - 1;
            } else {
                maxf = std::max(maxf, f[v]);
            }
        }
        if (need > -1) {
            if (maxf >= need) f[u] = 0;
            else f[u] = -need;
        } else {
            f[u] = maxf + 1;
        }
        // printf("%d: %d %d %d\n", u, maxf, need, f[u]);
        return true;
    }
 
    bool check(int mid)
    {
        int n = e.size();
        vector<int> len(k);
        // printf("[%d]: \n", mid);
        for (int i = 0; i < k; i++) {
            len[i] = mid / k + (i < mid % k);
            // printf("%d: %d\n", i, len[i]);
        }
        vector<int> f(n);
        bool flag = dfs(0, -1, len, f);
        if (f[0] < 0) return false;
        return flag;
    }
};