CF 1795F Blocking Chips

給定一個樹。有 $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;
    }
};