「做题记录」树上问题选做

· · 算法·理论

P4362 [NOI2002] 贪吃的九头龙

给出一棵节点数为 n 的有根树,根节点为 1,边带权。你需要将这棵树 m 染色,满足与根节点同色的节点数恰为 k。代价为两端点颜色相同的边的边权和,最小化代价并输出,或报告无解。

:::::success[题解] 不妨设根节点的颜色为 1。我们钦定 k 个节点的颜色为 1,则剩余点形成一个森林,需要 m-1 染色。

据此设计树形 DP:f_{0/1,u,i} 表示考虑 u 的子树,u 节点染色是否染成 1,子树内选择 i 个染成 1 的最小代价。枚举儿子 v 并合并 DP 数组,转移是 (\min,+) 卷积:

f_{0/1,u,i+j} \gets f_{0/1,u,i}+f_{0/1,v,j}+w

其中 w 为转移时 u \to v 的边是否产生贡献,容易根据 m 是否等于 2 以及 0/1 维的取值计算。

注意合并 DP 时需要新建数组,不然会覆盖原本的取值。无解容易判断。

正确的实现为树形背包复杂度,复杂度 O(n^2)。

:::::info[代码]

const int N = 305, inf = 0x3f3f3f3f;
int n, m, k;
vector<pair<int, int>> e[N];

int sz[N], f[2][N][N];
void dfs(int u, int fa) {
    f[0][u][0] = 0, f[1][u][1] = 0, sz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
        vector<int> f0(N, inf), f1(N, inf);
        for (int i = min(sz[u], k); i >= 0; i--) {
            for (int j = min(sz[v], k - i); j >= 0; j--) {
                chkmin(f0[i + j], f[0][u][i] + f[0][v][j] + (m == 2) * w);
                chkmin(f0[i + j], f[0][u][i] + f[1][v][j]);
                chkmin(f1[i + j], f[1][u][i] + f[0][v][j]);
                chkmin(f1[i + j], f[1][u][i] + f[1][v][j] + w);
            }
        }
        sz[u] += sz[v];
        copy(f0.begin(), f0.end(), f[0][u]), copy(f1.begin(), f1.end(), f[1][u]);
    }
}

void _main() {
    cin >> n >> m >> k;
    if (n - k < m - 1) return cout << -1, void();
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    } 
    memset(f, 0x3f, sizeof(f)), dfs(1, -1);
    cout << f[1][1][k];
} 

:::::

P9669 [ICPC 2022 Jinan R] DFS Order 2

给出一棵节点数为 n 的有根树,根节点为 1。对于每个 x=1,2,\cdots,n 和 p=1,2,\cdots,n 求出:在所有 DFS 序中,x 位于 DFS 序第 p 位的方案数。对 998244353 取模。

:::::success[题解] 根据 DFS 的规则,访问 x 之前必然访问了 x 的所有祖先和排在 x 之前的兄弟子树。

注意到总的 DFS 序数目为 \prod\limits_{u=1}^n |\operatorname{son}(u)|!,其中 \operatorname{son}(u) 是 u 的儿子集合。因此考虑计数转概率,计算 x 位于 DFS 序第 p 位的概率。

对于祖先节点 u,我们希望走向其儿子 v,并通向 x 的方向。记 m=|\operatorname{son}(u)|,则我们选出 i 个放在 v 前面,剩下 m-i-1 个放在后面。选出这种方案的概率系数为 \frac{i!(m-i-1)!}{m!}。

我们需要知道子树大小总和为 k 的情况数。记 f_{u,i,j} 为在 u 的 m 个儿子中选出 i 个儿子且子树大小之和恰为 j 的方案数。依次考虑儿子 v 然后用 01 背包合并:f_{u,i,j} \gets f_{v,i-1,j-sz_v}。

分析向 v 的路径时,我们不能算入 v 自身的方案。因此使用退背包,算出不含 v 的背包数组 g_{u,i,j},复杂度 O(n^3)。

得到以上信息后,将 g 与对应概率相乘并求和,得到总概率,答案容易计算。

:::::info[代码]

const int N = 505;
int n, sz[N], dep[N];
vector<int> e[N];
mint fac[N], ifac[N], h[N][N], ans[N][N];

void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa) continue;
        dep[v] = dep[u] + 1, dfs1(v, u), sz[u] += sz[v];
    }
}
void dfs2(int u, int fa) {
    if (e[u].size() == 1 && e[u][0] == fa) return;
    int m = u == 1 ? e[u].size() : e[u].size() - 1;
    vector<vector<mint>> f(m + 5, vector<mint>(sz[u] + 5));
    f[0][0] = 1;
    int sum = 0;
    for (int v : e[u]) {
        if (v == fa) continue;
        sum += sz[v];
        for (int i = m; i >= 1; i--) {
            for (int j = sum; j >= sz[v]; j--) f[i][j] += f[i - 1][j - sz[v]];
        }
    }
    for (int v : e[u]) {
        if (v == fa) continue;
        auto g = f;
        for (int i = 1; i <= m; i++) {
            for (int j = sz[v]; j <= sum; j++) g[i][j] -= g[i - 1][j - sz[v]];
        }
        vector<mint> p(sum + 5);
        for (int j = 0; j <= sum - sz[v]; j++) {
            for (int i = 0; i < m; i++) p[j] += g[i][j] * fac[i] * fac[m - i - 1] * ifac[m];
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= sum - sz[v] && i + j <= n; j++) h[v][i + j] += h[u][i] * p[j];
        }
        dfs2(v, u);
    }
}

void _main() {
    fac[0] = ifac[0] = 1;
    for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i, ifac[i] = ~fac[i];
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    h[1][0] = 1, dfs1(1, -1), dfs2(1, -1);
    mint t = fac[e[1].size()];
    for (int i = 2; i <= n; i++) t *= fac[e[i].size() - 1];
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i <= n; i++) {
            int pos = 1 + dep[u] + i;
            if (pos <= n) ans[u][pos] += h[u][i] * t; 
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << ans[i][j] << ' ';
        cout << '\n';
    }
} 

:::::

CF2068D Morse Code

给出 n 个实数 f_i。你需要为每个 i 分配一个字符串 s_i,使得不存在 i \ne j 满足 s_i 是 s_j 的前缀。字符集为 \{\tt{.},\tt{-}\}。其中 \tt{.} 的代价为 1,\tt{-} 的代价为 2,字符串的代价为其中字符代价之和。

设 s_i 的代价为 c_i,最小化 \sum\limits_{i=1}^n f_ic_i,构造方案并输出。

:::::success[题解] 你说的对,但 O(n^4) 过了。

下面称 \tt{.} 为 \tt{0},\tt{-} 为 \tt{1},则需要构造若干 01 串。考虑建立 01-Trie,向左儿子走的代价为 1,向右儿子走的代价为 2。记节点 u 到根节点的距离为 d_u,问题转化为在 01-Trie 上选择若干无祖先—后代关系的点,最小化 \sum f_u d_u。

我们肯定不能显式建立 01-Trie。因此考虑直接搜索,逐层构建 01-Trie。接下来有一个观察:f_i 越大的节点,其在 trie 上的深度越浅。证明考虑排序不等式。

因此,按 f_i 降序排序,每次在当前层分配 i 个节点时直接选择最大的 i 个点即可。

用四元组 (\text{k},\text{cur},\text{nxt},\text{dep}) 作为搜索状态,表示当前还有 \text{k} 个位置没有分配,当前层可以操作 \text{cur} 个点,下一层可以操作 \text{nxt} 个点,当前深度为 \text{dep}。

状态数是 O(n^4) 的。事实上,我们可以使用贡献提前计算的 trick:当 trie 向下推进一层时,所有尚未分配的字符,最终的编码长度都至少增加了 1。对 f 做一个后缀和,然后可以直接计算这一部分的代价,没有必要记录 \text{dep} 了。

对于三元组 (\text{k},\text{cur},\text{nxt}),我们枚举当前层有 i 个节点继续向下进行转移。如果搜索有环,则绕环一定不优,可以剪枝。并且将答案记忆化,到达已经搜索过的点直接返回。

这里状态数为 O(n^3),转移带 O(n),总体复杂度 O(n^4)。构造方案时,对于每个三元组 (\text{k},\text{cur},\text{nxt}) 记录最优决策点 i,然后推回去即可。

:::::

:::::info[代码]

const int N = 255;
const double inf = 1e18;
using node = pair<double, int>;

int n; node a[N];
double suf[N];
string ans[N];

int vis[N][N][N], opt[N][N][N];
double mem[N][N][N];
double dfs(int k, int cur, int nxt) {
    if (k == n) return 0;
    if (cur == 0 && nxt == 0) return inf;
    if (vis[k][cur][nxt] == 1) return inf;
    if (vis[k][cur][nxt] == 2) return mem[k][cur][nxt];
    vis[k][cur][nxt] = 1;
    double res = inf; int p = -1;
    for (int i = 0; i <= min(n - k, cur); i++) {
        int nk = k + cur - i;
        double cost = suf[nk + 1] + dfs(nk, min(nxt + i, n - nk), min(i, n - nk));
        if (cost < res) res = cost, p = i;
    }
    vis[k][cur][nxt] = 2;
    return opt[k][cur][nxt] = p, mem[k][cur][nxt] = res;
}
void work() {
    vector<string> cur = {""}, nxt;
    for (int k = 0; k < n; ) {
        int i = opt[k][min<int>(cur.size(), n - k)][min<int>(nxt.size(), n - k)];
        vector<string> nnxt;
        for (int j = 0; j < i; j++) {
            nxt.emplace_back(cur[j] + '.');
            nnxt.emplace_back(cur[j] + '-');
        }
        int cnt = min<int>(cur.size(), n - k) - i;
        for (int j = 0; j < cnt; j++) {
            ans[a[k + j + 1].second] = cur[i + j];
        }
        k += cnt, cur.swap(nxt), nxt.swap(nnxt);
    }
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + n + 1, greater<node>());
    for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + a[i].first;
    dfs(0, 1, 0), work();
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
}

:::::

P9527 [JOIST 2022] 洒水器 / Sprinkler

给出一棵 n 个节点的无根树,点有点权 a_i。q 次操作:

  1. 给出 u,k,x,将距离 u 不超过 k 的点的点权乘 x。
  2. 给出 u,查询 u 的点权。

对给出的模数取模,不保证模数为质数。

:::::success[题解] 在树上每个节点维护若干标记:将 u 子树中距离恰为 i 的点乘上 f_{i,u}。

修改时对这些标记进行更新:f_{u,k}, f_{u,k-1}, f_{\operatorname{fa}(u),k-2},f_{\operatorname{fa}(u),k-3},\cdots,显然只会做 O(k) 次。

标记下传很困难,因此永久化。查询时需要跳父亲来得到标记。也只会跳 O(k) 次。

这个做法可以做到不重不漏。复杂度 O(n+qk)。

:::::info[代码]

const int N = 2e5 + 5;
int n, _mod, q, fa[N];
vector<int> e[N];
mint a[N], tag[41][N];

void dfs(int u) {
    for (int v : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, dfs(v);
    }
}

void _main() {
    cin >> n >> _mod, mint::set_mod(_mod);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> a[i];
    fa[1] = -1, dfs(1);
    for (int i = 0; i <= 40; i++) fill(tag[i], tag[i] + n + 1, 1);
    cin >> q;
    for (int opt, u, k, x; q--; ) {
        cin >> opt >> u;
        if (opt == 1) {
            cin >> k >> x;
            for (int i = 0; i <= k; i++, u = fa[u]) {
                if (fa[u] == -1) {
                    for (int d = 0; d <= k - i; d++) tag[d][u] *= x;
                    break;
                }
                tag[k - i][u] *= x;
                if (k - i - 1 >= 0) tag[k - i - 1][u] *= x;
            }
        } else {
            mint res = a[u];
            for (int i = 0; i <= 40 && u != -1; i++, u = fa[u]) res *= tag[i][u];
            cout << res << '\n';
        }
    }
}

:::::

P9755 [CSP-S 2023] 种树

给定一棵节点树为 n 的有根树,根节点为 1。每个节点上有一个任务。每个时刻,你可以标记一个节点,要求这个节点为根或其父亲已被标记。

对于被标记的节点,在第 x 个时刻任务的完成度将会增加 \max(1,b_i+x\times c_i)。目标为所有节点 i 上任务的完成度 \ge a_i。初始时任务完成度均为 0。

求完成所有任务的最小时间。

:::::success[题解] 考虑特殊性质 A,即 c_i=0 的情形。此时可以求出完成每个任务所需的时间 t_i = \lceil \frac{a_i}{b_i} \rceil。考虑如下贪心:将节点按照 t_i 升序排序,依次扫描每个节点,将对应的根链全部标记。

由于答案取决于每个任务的最晚完成时间,因此考虑调整后一定不优,可以说明这个做法的正确性。

上述算法直观的实现是树剖线段树,复杂度 O( n \log^2 n)。但是这个过于魔怔了,考虑直接暴力,由于每个点最多被标记一次,跳父亲一共只有 O(n) 次,因此复杂度正确。

接下来考虑特殊性质 B,即链的情形。考虑二分答案 x,对于每个点求出 f(x,l,r),表示节点 x 在时间段 [l,r] 完成度的变化量,即可进行 check。下面讲解 f 的计算。

可以做到 O(1) 求解。注意计算 f 的过程需要 int128。

考虑将 A & B 的做法结合起来。我们二分答案 x 转判定,判定时再对每个节点二分一次,通过 f 求出每个节点最晚完成任务的时间 t_i。

按照 t_i 升序排序,使用 A 性质的均摊 O(n) 做法即可,复杂度 O(n \log n \log V)。

:::::info[代码]

const int N = 1e5 + 5;
int n, fa[N], tag[N];
vector<int> e[N];
void dfs(int u) {
    for (int v : e[u]) if (v != fa[u]) fa[v] = u, dfs(v); 
}
i64 a[N], b[N], c[N], t[N];
i128 f(int x, i128 l, i128 r) {
    if (c[x] >= 0) return (r - l + 1) * b[x] + (r - l + 1) * (l + r) / 2 * c[x];
    i64 k = (1 - b[x]) / c[x];
    if (k < l) return r - l + 1;
    if (k > r) return (r - l + 1) * b[x] + (r - l + 1) * (l + r) / 2 * c[x];
    return (k - l + 1) * b[x] + (k - l + 1) * (l + k) / 2 * c[x] + r - k;
}

bool check(int x) {
    for (int i = 1; i <= n; i++) {
        if (f(i, 1, x) < a[i]) return false;
        int l = 1, r = n;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (f(i, mid, x) >= a[i]) l = mid + 1, t[i] = mid;
            else r = mid - 1;
        }
    }
    fill(tag + 1, tag + n + 1, 0);
    vector<int> vec(n); iota(vec.begin(), vec.end(), 1);
    sort(vec.begin(), vec.end(), [](int x, int y) -> bool {
        return t[x] < t[y];
    });
    int cur = 0;
    for (int i : vec) {
        if (tag[i]) continue;
        stack<int> st;
        for (int j = i; j != -1 && !tag[j]; j = fa[j]) st.emplace(j);
        while (!st.empty()) {
            int u = st.top(); st.pop();
            if (++cur > t[u]) return false;
            tag[u] = true;
        }
    } return true;
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    fa[1] = -1, dfs(1); 
    int l = 0, r = 1e9, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) res = mid, r = mid - 1;
        else l = mid + 1;
    } cout << res;
} 

:::::

P5290 [十二省联考 2019] 春节十二响

给出一棵以 1 为根的有根树,节点数为 n,点带权 a_i。你需要将这些节点划分为若干个集合 S_1,S_2,\cdots,S_k,满足集合内部不存在祖先—后代关系。最小化 \sum\limits_{i=1}^k \max\limits_{u \in S_i} a_u 并输出。

:::::success[题解]

对于点 u 的两个儿子 x,y,由于集合不能存在祖先—后代关系,因此 x 的答案需要与 y 合并。

注意到 \max 的四边形不等式 a<b<c<d \implies \max(a,b)+\max(c,d) < \max(a,c)+\max(b,d)。根据 exchange argument 的理论,将 x,y 的答案升序排序后依次配对,在局部即为最优。

接下来证明局部最优不会影响祖先答案。将不升序列 a_i,b_i 合并后的 c_i=\max(a_i,b_i) 也是一个不升序列。因此采用其他合并方法得到 c'_i 并降序排序后必然有 c'_i \ge c_i。

子树 u 继续向上合并时,提供一个更劣的 c'_i 一定不优。因此上传 c_i 就是全局最优。

直接模拟即可 O(n^2)。用启发式合并维护优先队列就有 O(n \log n)。

:::::info[代码]

const int N = 2e5 + 5;
int n, a[N];
vector<int> e[N];
priority_queue<int> q[N];
void join(int u, int v) {
    if (q[u].size() < q[v].size()) swap(q[u], q[v]);
    vector<int> vec;
    while (!q[v].empty()) {
        vec.emplace_back(max(q[u].top(), q[v].top()));
        q[u].pop(), q[v].pop();
    }
    for (int i : vec) q[u].emplace(i);
}
void dfs(int u) {
    for (int v : e[u]) dfs(v), join(u, v);
    q[u].emplace(a[u]);
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int v = 2, u; v <= n; v++) cin >> u, e[u].emplace_back(v);
    dfs(1); i64 res = 0;
    while (!q[1].empty()) res += q[1].top(), q[1].pop();
    cout << res;
} 

:::::

P5521 [yLOI2019] 梅深不见冬

给出一棵节点数为 n 的有根树,根节点为 1,带点有点权 a_u。

你初始持有 f_u 个物品,位于节点 1。你可以在树上进行游走,可以选择进入一个未进入的子节点,或者回到父节点。

你需要在每个节点上放置若干物品。对于非叶节点 u,允许在其上放置物品的条件为:每个子节点 v 的物品数都恰好为 a_v。

你可以在任意时刻回收任意节点上的物品,且不需要走到对应点。

对于 u=1,2,\cdots,n,求出在节点 u 上放置 a_u 个物品所需的 f_u 的最小值。

:::::success[题解] 考虑树形 DP,设 f_u 为节点答案。注意到 u 点可回收的物品数恰好为 a_u。我们钦定某种顺序,依次游走子树 v_1,v_2,\cdots,v_k,那么有转移:

\begin{aligned} f_u &\gets \sum_{i=1}^{x-1} a_{v_i}+f_{v_x}, x =1,2,\cdots,k\\ f_u &\gets \sum_{i=1}^k a_i+f_u \end{aligned}

根据木桶原理这里做的是 chkmax。前面这个求和式表示之前回收的物品总数,容易前缀和维护。

现在考虑如何对儿子 v_i 排序,想到用 exchange argument,考虑局部,设两儿子为 x,y。

记前面的和式为 S,则讨论先 x 后 y 和先 y 后 x 所造成的局部 \max:

令 \max(f_x,a_x+f_y)<\max(f_y,a_y+f_x)。

根据 a_x,a_y \ge 1,我们有 f_x < f_x+a_y \land a_x+f_y>f_y,故原不等式写为

a_x+f_y<a_y+f_x \iff f_x-a_x > f_y-a_y

得证,按 f_v-a_x 降序排序即可,显然严格全序。

复杂度 O(n \log n)。用邻项交换贪心来确定 DP 转移顺序,十分精妙。

:::::info[代码]

const int N = 1e5 + 10;
int n, a[N];
vector<int> e[N];
i64 f[N];

void dfs(int u) {
    for (int v : e[u]) dfs(v);
    sort(e[u].begin(), e[u].end(), [](int x, int y) -> bool {
        return f[x] - a[x] > f[y] - a[y]; 
    });
    i64 sum = 0;
    for (int v : e[u]) f[u] = max(f[u], sum + f[v]), sum += a[v];
    f[u] = max(f[u], sum + a[u]);
}

void _main() {
    cin >> n;
    for (int i = 2, x; i <= n; i++) cin >> x, e[x].emplace_back(i);
    for (int i = 1; i <= n; i++) cin >> a[i];
    dfs(1);
    for (int i = 1; i <= n; i++) cout << f[i] << ' '; 
}

:::::

P3574 [POI 2014] FAR-FarmCraft

给出一棵 n 个点的有根树,根节点为 1。你从根节点开始游走,走过一条边的代价为 1,必须经过每条边恰好两次。

每个点有点权 a_i,当你游走到该点时,该点上会开始一个时长为 a_i 的任务。最终回到根节点后,开始一个时长为 a_1 的任务。最小化所有点完成任务的时间并输出。

:::::success[题解] 考虑树形 DP,记 f_u 为 u 子树内的最大时间,g_u 为将子树内游走完成的总时间。如果可以钦定一个游走儿子的顺序,就有转移:

\begin{aligned} f_u &\gets \max(f_u,f_v+g_u+1)\\ g_u &\gets g_v+2 \end{aligned}

关键在于确定 f。考虑和上一题一样做 exchange argument。考虑局部 x,y 有:

钦定前者更优,于是

f_y+g_u+g_x+3 <f_x+g_u+g_y+3 \iff f_x-g_x>f_y-g_y
这是一个严格偏序,按 f_u-g_u 降序排序,然后做 DP 转移即可。复杂度 O(n \log n)。

:::::info[代码]

const int N = 5e5 + 5;
int n, a[N], f[N], g[N];
vector<int> e[N];
void dfs(int u, int fa) {
    if (fa != -1) f[u] = a[u];
    vector<int> vec;
    for (int v : e[u]) {
        if (v == fa) continue;
        dfs(v, u), vec.emplace_back(v);
    }
    sort(vec.begin(), vec.end(), [](int x, int y) -> bool {
        return f[x] - g[x] > f[y] - g[y];
    });
    for (int v : vec) chkmax(f[u], f[v] + g[u] + 1), g[u] += g[v] + 2;
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    dfs(1, -1);
    cout << max(f[1], a[1] + g[1]);
}

:::::

ABC376G Treasure Hunting

给出一棵 n+1 个点的有根树,根节点为 0。你从根节点开始游走,只能游走到父亲已经走过的点。每个点有 \frac{a_i}{\sum a} 的概率为关键点,最小化到达关键点步数的期望值并输出,对 998244353 取模。

多测,\sum n \le 2 \times 10^5,2 秒,1024 MB。

:::::success[题解] 树上 exchange argument 模板题。

将所有概率乘上 \sum a,答案再除回去。然后把题意翻译成:找到一个拓扑序 b_i,最小化 \sum\limits_{i=1}^n a_ib_i。

拓扑序是合并连通块的过程,合并的顺序考虑用 exchange argument 确定。记 c_A 为连通块节点数目,w_A 为块中点权和。对于块 A,B,将其交换位置的答案变化量为

c_B w_A-c_A w_B

钦定上式 <0 移项得 c_B w_A<c_A w_B \iff \frac{c_B}{w_B}<\frac{c_A}{w_A}。这是一个严格全序,符合要求。

可以用并查集 + set 来维护。初始时,将所有节点加入集合,其中 c_I=1,w_I=a_i,按照 \frac{w_A}{c_A} 为关键字降序排序。

每次取出最大的 u,将 u 合并到父节点块 v 中。这里 v 是这个连通块的代表元,使用并查集找到。合并后 v 的代价改变,删去旧值并插入新值即可。

总复杂度 O(n \log n)。

:::::info[代码]

const int N = 2e5 + 5;
int n, p[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
i64 a[N], c[N], w[N];

struct node {
    i64 w, c; int id;
    node(i64 x = 0, i64 y = 0, int z = 0) : w(x), c(y), id(z) {}
    bool operator< (const node& a) const {
        if (w * a.c != c * a.w) return w * a.c > c * a.w;
        return id < a.id;
    }
};
set<node> q;

void _main() {
    cin >> n;
    iota(fa, fa + n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    mint sum = accumulate(a + 1, a + n + 1, mint(0)), cost = sum;
    copy(a, a + n + 1, w), fill(c, c + n + 1, 1);
    c[0] = 0, w[0] = 0;
    for (int i = 1; i <= n; i++) q.emplace(w[i], c[i], i);
    while (!q.empty()) {
        int u = q.begin()->id; q.erase(q.begin());
        int v = find(p[u]);
        if (v != 0) q.erase(node(w[v], c[v], v));
        cost += c[v] * w[u];
        c[v] += c[u], w[v] += w[u], fa[find(u)] = find(v);
        if (v != 0) q.emplace(w[v], c[v], v); 
    }
    cout << cost / sum << '\n';
} 

:::::

QOJ8130 Yet Another Balanced Coloring Problem

给出两棵大小为 n,m 的有根树,根节点分别为 n 和 m。保证两棵树的叶子节点均为 1,2,\cdots,k。构造一种对叶子的黑白染色方案,使得对于每棵树,每个子树中黑点与白点的数目相差不超过 1。输出方案或报告无解。

多测,\sum (n+m) \le 2 \times 10^5,1 秒,256 MB。

:::::success[题解] 先考虑一棵树的情形。

叶向树问题,自底向上贪心。对于当前子树中未处理的叶子,我们在新图 G 中将两个叶子连一条边,钦定其颜色不同。对 G 做黑白染色就得到了构造,容易证明合法且有解。

两棵树的情形,考虑套用上面的做法。正确性仍然显然。

并且可以说明,这样做一定有解。注意到每个点的度数 \le 2,则 G 中链的情况是平凡的。而 DFS 过程相当于将两个匹配合并,有环也必为偶环。

:::::info[代码]

const int N = 1e5 + 5;
int n, m;
vector<int> e1[N], e2[N], e[N];

int dfs1(int u, vector<int>* et) {
    if (et[u].empty()) return u;
    vector<int> vec;
    for (int v : et[u]) {
        int x = dfs1(v, et);
        if (x != -1) vec.emplace_back(x);
    }
    while (vec.size() > 1) {
        int x = vec.back(); vec.pop_back();
        int y = vec.back(); vec.pop_back();
        e[x].emplace_back(y), e[y].emplace_back(x);
    }
    return vec.empty() ? -1 : vec[0];
}

int col[N];
void dfs2(int u) {
    for (int v : e[u]) {
        if (col[v] != -1) continue;
        col[v] = col[u] ^ 1, dfs2(v);
    }
}

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= max(n, m); i++) e1[i].clear(), e2[i].clear(), e[i].clear();
    for (int v = 1, u; v < n; v++) cin >> u, e1[u].emplace_back(v);
    for (int v = 1, u; v < m; v++) cin >> u, e2[u].emplace_back(v);
    dfs1(n, e1), dfs1(m, e2);
    int k = 0;
    for (int i = 1; i <= min(n, m); i++) if (e1[i].empty()) k++;
    fill(col + 1, col + k + 1, -1);
    for (int i = 1; i <= k; i++) {
        if (col[i] != -1) continue;
        col[i] = 0, dfs2(i); 
    }
    for (int i = 1; i <= k; i++) cout << (col[i] ? 'R' : 'B');
    cout << '\n';
}

:::::

P7600 [APIO2021] 封闭道路

给出一棵 n 个节点的无根树,边带权。对于每个 k=0,1,\cdots,n-1 求出:删去一些边使得每个点的度数 \le k,最小化删去的边权之和。

:::::success[题解] 将问题转化为最大化保留边的边权和。

首先是一个暴力 DP:记 f_{u,k} 为不保留 u 处返祖边时,子树内的答案;g_{u,k} 为保留 u 处返祖边时,子树内的答案。

考虑先将儿子全选 f_{u,k},然后反悔,选出 g_{v,k}+w-f_{u,k} 最大的若干个。f_{u,k} 应该由 u 子树中前 k 大的值转移,g_{u,k} 则由前 k-1 大的值转移。

复杂度 O(n^2 \log n),可以获得 24pts。

我们注意到,度数 \le k 的点不受约束。因此考虑枚举 k 时对度数 >k 的点建立虚树,然后在虚树上 DP。由于每个点只会出现度数次,虚树的大小之和就是 O(n) 的。

沿用 f_u 和 g_u 的状态。当我们位于节点 u 时,其儿子被分为两类:

那么只需要维护前 k 大数的和就能转移。在建虚树时修改权值,对每个节点开一棵权值线段树维护,复杂度 O(n \log n)。

:::::info[代码]

const int N = 1e5 + 5, M = 1e9;
int n, deg[N];
vector<pair<int, int>> e[N];

int dn, fa[N], sz[N], dep[N], son[N], top[N], dfn[N], wei[N];
void dfs1(int u) {
    sz[u] = 1, dfn[u] = ++dn;
    for (auto [v, w] : e[u]) {
        if (v == fa[u]) continue;
        fa[v] = u, wei[v] = w, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (auto [v, w] : e[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    } return dep[u] < dep[v] ? u : v;
}

#define ls lson[rt]
#define rs rson[rt]
int tot, rt[N], lson[N << 6], rson[N << 6], cnt[N << 6];
i64 sum[N << 6]; 
void insert(i64 x, i64 l, i64 r, int& rt) {
    if (!rt) rt = ++tot;
    cnt[rt]++, sum[rt] += x;
    if (l == r) return;
    i64 mid = (l + r) >> 1;
    if (x <= mid) insert(x, l, mid, ls);
    else insert(x, mid + 1, r, rs);
}
void remove(i64 x, i64 l, i64 r, int& rt) {
    if (!rt) rt = ++tot;
    cnt[rt]--, sum[rt] -= x;
    if (l == r) return;
    i64 mid = (l + r) >> 1;
    if (x <= mid) remove(x, l, mid, ls);
    else remove(x, mid + 1, r, rs);
}
i64 ask(int k, i64 l, i64 r, int rt) {
    if (rt == 0 || k <= 0) return 0;
    if (cnt[rt] <= k) return sum[rt];
    if (l == r) return l * k;
    i64 mid = (l + r) >> 1;
    if (cnt[rs] >= k) return ask(k, mid + 1, r, rs);
    return sum[rs] + ask(k - cnt[rs], l, mid, ls);
}

bool keep[N];
vector<int> nd[N], ev[N], dr[N];
i64 f[N], g[N];

void dfs3(int u, int k) {
    f[u] = g[u] = 0;
    i64 sum = 0;
    vector<i64> son;
    for (int v : ev[u]) {
        dfs3(v, k);
        if (fa[v] == u && keep[v]) sum += f[v], son.emplace_back(g[v] + wei[v] - f[v]);
        else sum += f[v];
    }
    if (keep[u]) {
        for (i64 x : son) if (x > 0) insert(x, 1, M, rt[u]);
        f[u] = sum + ask(k, 1, M, rt[u]), g[u] = sum + ask(k - 1, 1, M, rt[u]);
        for (i64 x : son) if (x > 0) remove(x, 1, M, rt[u]);
    } else {
        f[u] = sum, g[u] = 0;
    }
}

vector<i64> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) {
    n = N; i64 sum = 0;
    for (int i = 0; i < n - 1; i++) {
        int u = U[i] + 1, v = V[i] + 1, w = W[i];
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
        deg[u]++, deg[v]++, sum += w;
    }
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < deg[u]; i++) nd[i].emplace_back(u);
        dr[deg[u]].emplace_back(u);
    }
    dfs1(1), dfs2(1, 1);
    vector<i64> ans(n); ans[0] = sum;
    i64 bas = 0;
    fill(keep + 1, keep + n + 1, true);
    for (int k = 1; k < n; k++) {
        for (int u : dr[k]) {
            keep[u] = false;
            for (auto [v, w] : e[u]) {
                if (keep[v]) insert(w, 1, M, rt[v]);
                else bas += w;
            }
        }
        vector<int>& a = nd[k];
        if (a.empty()) {
            ans[k] = sum - bas;
            continue;
        }
        sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
        int len = a.size();
        for (int i = 0; i < len - 1; i++) a.emplace_back(lca(a[i], a[i + 1]));
        sort(a.begin(), a.end(), [](int u, int v) {return dfn[u] < dfn[v];});
        a.erase(unique(a.begin(), a.end()), a.end());
        for (int i = 0; i < (int)a.size() - 1; i++) 
            ev[lca(a[i], a[i + 1])].emplace_back(a[i + 1]);
        dfs3(a[0], k);
        ans[k] = sum - bas - f[a[0]];
        for (int i : a) ev[i].clear();
    }
    return ans;
}

:::::

P3479 [POI 2009] GAS-Fire Extinguishers

给出一棵节点数为 n 的有根叶向树,根节点为 1。你需要在某些节点放置任意数量的元素,每个元素可以被分配给距离 \le k 的节点,且最多分配给 s 个不同节点。要求每个节点至少被分配到一个元素。最小化放置元素的总数目并输出。

::::::success[题解] 叶向树上的问题,考虑自底向上贪心。

我们声称,元素应当尽量放置在深度较小的节点上。对于节点 x,若其子树中仍存在距离 =k 的点 u 未分配,则必须在 x 处放置元素并分配给 u。

可以用调整法说明上述策略的正确性。假设存在最优解,将 x 替换为在其子树中的点 v,并将 v 的元素分配给 u。记 d(u,v) 为两点间距离,则 d(u,v)<k。

现在将 v 上的元素移动到 x,我们要证明这仍是一个最优解,即说明被 v 覆盖的元素可以被 x 覆盖:

说明这一做法的正确性后,考虑设计树形 DP 来执行策略。

记 f_{i,x} 为在 x 子树内,距离 x 为 i 的可分配数,g_{i,x} 为子树内距离为 i 的需求数目。DP 转移时,讨论在 x 处新增元素,并且在 x 处将余量 f_{i,x} 与需要 g_{j,x} 进行匹配。

一种错误的策略为:将满足 i+j \le k 的所有余量—需求关系在当前 LCA 全部匹配。这种贪心会将极好的余量分配给容易满足的需求,从而导致较难满足的需求只能通过放置元素来解决。

事实上,我们只应该在如下两种情况时进行匹配:

  1. 在 i+j \in \{k-1,k\} 时将其匹配。因为如果再往祖先移动,就有 i \gets i+1,j \gets j+1,此时 i+j>k 失去匹配机会;
  2. 存在 g_{k,x}>0 时,再向上走就无法处理这一需求,所以必须在 x 处新建元素 f_{0,x} 将其匹配。

正确性容易说明,考虑上述过程相当于贡献延后 DP,且所有余量—需求关系最终都会在根节点正确处理。

自底向上 DFS,对于当前节点 x 有:

注意在根节点处,我们需要进行剩余匹配。首先将所有 i+j \le k 的 g_{i,u} 和 f_{j,u} 匹配后,求出剩余需求数目 a,将 \lceil \frac{a}{s} \rceil 加入答案。

按照上述过程实现,可以做到 O(nk)。

:::::info[代码]

const int N = 1e5 + 5;
int n, s, k;
vector<int> e[N];
i64 ans, f[21][N], g[21][N];
void dfs(int u, int fa) {
    for (int v : e[u]) { 
        if (v == fa) continue;
        dfs(v, u);
        for (int i = 0; i < k; i++) f[i + 1][u] += f[i][v], g[i + 1][u] += g[i][v];
    }
    g[0][u] = 1;
    for (int i = k; i >= 0; i--) {
        for (int j : {k - i, k - i - 1}) {
            if (j < 0) continue;
            i64 a = min(g[i][u], f[j][u]);
            g[i][u] -= a, f[j][u] -= a;
        }
        if (i == k && g[k][u] > 0) {
            i64 a = (g[k][u] + s - 1) / s;
            ans += a, f[0][u] += a * s - g[k][u], g[k][u] = 0;
        }
    }
}

void _main() {
    cin >> n >> s >> k;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    dfs(1, -1);
    for (int i = k; i >= 0; i--) {
        for (int j = k - i; j >= 0; j--) {
            i64 a = min(g[i][1], f[j][1]);
            g[i][1] -= a, f[j][1] -= a;
        }
    }
    i64 rem = 0;
    for (int i = 0; i <= k; i++) rem += g[i][1];
    cout << ans + (rem + s - 1) / s;
} 

:::::

P4785 [BalticOI 2016] 交换 (Day2)

给出一个长为 n 的排列 a_i。有 n-1 轮操作,第 k 次操作可以交换 a_k 和 a_{\lfloor k/2\rfloor}。你需要最小化最终排列的字典序并输出。

:::::success[题解] 思维自然且很有启发性的好题,点赞!

题目中 i \to \lfloor i/2 \rfloor 的交换方式让我们联想到完全二叉树的堆式存储:将 \lfloor i/2 \rfloor 视为 i 的父亲,i 的左右儿子为 2i,2i+1。

对原排列建立完全二叉树,根节点为 1,则题目转化为最小化层序遍历字典序。

我们按前序遍历的顺序依次考虑每个节点 i,则其最终值有三种可能:x=a_i,y=a_{2i},z=a_{2i+1}。贪心地,我们先让 i 处的值最小,字典序一定更优。

这里需要说明一下,直接将较小值作为左子树根是错误的,因为较小值可能在左子树中被替换。

我们将一个值沉入一棵子树,其必然经历若干次替换后停止在某个位置。这个位置可以通过模拟上述流程算出。

设 f(u,x) 为值 x 沉入 u 子树后的最终位置。在节点 i 处,假定 z 是最小值,不妨设 x<y ,则我们计算出 f(2i,x) 和 f(2i+1,x),然后将 x 沉入较小的一边即可。

对于 f(u,x) 的求解,可以模拟上述递归流程,其会在 z 成为最小值时产生 3 个分支,由递归式 T(n)=3T(n/2)+O(1) 解得复杂度 O(n^{\log_2 3}) \approx O(n^{1.585})。加上递归求解,总复杂度为 O(n^{1.585} \log n),可以卡过。

我们注意到 x 一定来源于 u 的祖先节点,这只会有 O(\log n) 个,所以可以对 (u,x) 二元组记忆化。根据记搜实现方式,复杂度为 O(n \log^2 n) \sim O(n \log n)。由于哈希表常数太大,使用 map 实现多一只 log 但跑的更快。

:::::info[代码]

const int N = 2e5 + 5;
int n, a[N], ans[N];

umap<int, int> mem[N];
int f(int u, int val) {
    int ls = u << 1, rs = u << 1 | 1;
    if (ls > n) return u;
    if (rs > n) return val < a[ls] ? u : f(ls, val);
    if (mem[u].find(val) != mem[u].end()) return mem[u][val];
    int m = min({val, a[ls], a[rs]});
    if (m == val) return mem[u][val] = u;
    if (m == a[ls]) return mem[u][val] = f(ls, val);
    if (val < a[ls]) return mem[u][val] = min(f(ls, val), f(rs, val));
    return mem[u][val] = f(ls, a[ls]) < f(rs, a[ls]) ? f(rs, val) : f(ls, val);
}
void solve(int u, int val) {
    int ls = u << 1, rs = u << 1 | 1;
    if (ls > n) return ans[u] = val, void();
    if (rs > n) {
        int v = a[ls];
        if (v < val) swap(v, val);
        return ans[u] = val, solve(ls, v), void();
    }
    int m = min({val, a[ls], a[rs]});
    if (m == val) {
        ans[u] = val, solve(ls, a[ls]), solve(rs, a[rs]);
    } else if (m == a[ls]) {
        ans[u] = a[ls], solve(ls, val), solve(rs, a[rs]); 
    } else {
        ans[u] = a[rs];
        int x = val, y = a[ls];
        if (x > y) swap(x, y);
        if (f(ls, x) < f(rs, x)) solve(ls, x), solve(rs, y);
        else solve(ls, y), solve(rs, x);
    }
} 

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = 1e9, solve(1, a[1]);
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
} 

:::::

P5311 [Ynoi2011] 成都七中

给你一个 n 个节点的无根树,点有颜色,q 次查询给出 l,r, x,求保留 [l,r] 中的节点后 x 所在连通块颜色数。

:::::success[题解]

记 S_{x,[l,r]} 为保留 [l,r] 后 x 的可达点集,有关键观察:\forall y \in S_{x,[l,r]}, S_{x,[l,r]}=S_{y,[l,r]}。

点分治起手,设分治中心为 c,则将 c 作为代表元求解子树中的问题。具体地,对于子树中的询问 (l,r,x),我们判断是否有 c \in S_{x,[l,r]},若满足条件则求解 S_{c,[l,r]} 的答案,若不满足则作为子问题分治处理。

现在问题转化为:求从 c 出发,只经过 [l,r] 的可达点集中的颜色数。

设 (u,v) 两点间的路径为 p_1,p_2,\cdots,p_k,则 (u,v) 可达当且仅当 \forall 1 \le i \le k, p_i \in [l,r],即 [\min p, \max p] \subseteq [l,r]。

于是从 c 开始自顶向下维护两个值 mx_u, mn_u,表示 u 到 c 的路径上的最大 / 最小编号,此时 u 带贡献的必要条件是 l \le mn_u \le mx_u \le r。用二维平面来刻画,将 (mn_u,mx_u) 作为一个点,问题即:在 x \le l, y\le r 的区域内数颜色。

将颜色去重后进行二维数点。对于同种颜色,若存在两点 (x_1,y_1),(x_2,y_2) 且 x_1 \le x_2, y_1 \le y_2,则 (x_2,y_2) 是无用的。去重以后,将查询按 l 降序排序,对 x 扫描线。

采用类似于 HH 的项链的处理方式,维护一个树状数组,同时记录每种颜色上一次出现的位置,激活新位置时要删除上一个位置。

按照上述过程实现,视 n,q,V 同阶复杂度 O(n \log^2 n)。

::::::

:::::info[代码]

const int N = 1e5 + 5;
using query = tuple<int, int, int, int>;  // {l, r, x, id}
using point = tuple<int, int, int>;  // {x, y, col}

struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x < N; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;

int n, q, col[N], ans[N];
vector<int> e[N];

int ctr, cur, sz[N], vis[N];
void dfs1(int u, int fa) {
    sz[u] = 1;
    for (int v : e[u]) {
        if (v == fa || vis[v]) continue;
        dfs1(v, u), sz[u] += sz[v];
    }
    if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {
    cur++;
    for (int v : e[u]) if (v != fa && !vis[v]) dfs2(v, u);
}

int mn[N], mx[N], bel[N];
void dfs3(int u, int fa, int minv, int maxv, int b, vector<int>& vec) {
    minv = min(minv, u), maxv = max(maxv, u);
    mn[u] = minv, mx[u] = maxv, bel[u] = b, vec.emplace_back(u);
    for (int v : e[u]) if (v != fa && !vis[v]) dfs3(v, u, minv, maxv, b, vec);
} 

int last[N];
vector<query> child[N];
vector<pair<int, int>> cp[N];
void update(int u, vector<query>& q, vector<pair<int, vector<query>>>& nxt) {
    vector<int> vec = {u};
    mn[u] = u, mx[u] = u, bel[u] = -1;
    for (int v : e[u]) {
        if (!vis[v]) dfs3(v, u, u, u, v, vec);
    }
    vector<query> now;
    for (auto& [l, r, x, id] : q) {
        if (l <= mn[x] && mx[x] <= r) now.emplace_back(l, r, x, id);
        else child[bel[x]].emplace_back(l, r, x, id);
    }
    for (int v : e[u]) {   // 下传询问
        if (vis[v] || child[v].empty()) continue;
        nxt.emplace_back(v, child[v]), child[v].clear();
    }

    // 扫描线
    vector<point> p;
    for (int v : vec) cp[col[v]].emplace_back(mn[v], mx[v]);
    for (int v : vec) {   // 去重
        if (cp[col[v]].empty()) continue;
        sort(cp[col[v]].begin(), cp[col[v]].end(), greater<pair<int, int>>());
        int ymin = 1e9;
        for (auto& [x, y] : cp[col[v]]) {
            if (y < ymin) ymin = y, p.emplace_back(x, y, col[v]);
        }
        cp[col[v]].clear();
    }
    sort(now.begin(), now.end(), greater<query>());
    sort(p.begin(), p.end(), greater<point>());

    int i = 0;
    vector<int> undo;
    for (auto& [l, r, x, id] : now) {
        for (; i < (int)p.size() && get<0>(p[i]) >= l; i++) {
            auto& [_, y, c] = p[i];
            if (last[c]) B.add(last[c], -1);
            last[c] = y, B.add(last[c], 1);
            undo.emplace_back(c);
        }
        ans[id] = B.ask(r);
    }
    for (int c : undo) if (last[c]) B.add(last[c], -1), last[c] = 0;
}

void solve(int u, vector<query>& q) {
    if (q.empty()) return;
    vis[u] = true;
    vector<pair<int, vector<query>>> nxt;
    update(u, q, nxt);
    for (auto& [v, vec] : nxt) {
        cur = ctr = 0, dfs2(v, u), dfs1(v, u);
        solve(ctr, vec);
    }
}

void _main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> col[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    vector<query> vec;
    for (int i = 1, l, r, x; i <= q; i++) {
        cin >> l >> r >> x;
        vec.emplace_back(l, r, x, i);
    }
    cur = n, dfs1(1, -1), solve(ctr, vec);
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n'; 
} 

:::::