CF 1795F Blocking Chips

标签: cf

给定一个树。有 个 chip,分别位于 ,且互不相同,在时间 个 chip 要移动到一个没有被任何 chip 到达过的地方,问在何时某个 chip 无法移动。

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

贪心,对于每个节点,尽量让其在子树内完成所需步数。令 表示可以从 节点往子树下走的步数,同时当 时表示 节点需要往上走的步数(的相反数)。

对于节点 ,如果儿子中存在有两个都要向上走,或本身就是 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;
    }
};