Codeforces 1856E2 复杂度分析 + DP

题意

传送门 Codeforces 1856E2 PermuTree (hard version)

题解

可以独立考虑每一个固定的 $p=lca(u,v)$ 对答案的贡献。可以观察到，对于 $p$ 的每一棵子树，其所有节点在最优情况下仅有 $a_p<a_v$ 或 $a_p>a_v$ 两种可能。那么需要在值域上将子树的节点左右划分，那么需要求解所有子树的子集中，子树规模 $s{z}_v$ 的和最接近所有子树和的 $1/2$ 的值 $x$，则对答案的贡献为 $x\ast (s{z}_p-1-x)$。对于上述背包问题，满足 $s{z}_u+\cdots +s{z}_v=s{z}_p-1$，可以做到 $O(s{z}_p\sqrt{s{z}_p})$，具体做法类似于二进制拆分，不断将相同的值合并，最终每一个不同的值仅有常数个，则不同的值数量为 $O(\sqrt{s{z}_p})$。

若存在 $s{z}_v\ast 2\ge s{z}_p-1$，则无需进行背包。考虑最坏情况，即平衡的多叉树，容易观察到所有背包 DP 的复杂度为 $O(n\sqrt{n})$， std::bitset 优化即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 1E6;template <int m = 1>
ll knapsack(int n, vector<int> &b) {if (m < n) {return knapsack<min(m * 2, N)>(n, b);}bitset<m + 1> bt;bt[0] = 1;for (int x : b) {bt |= bt << x;}int res = -1;for (int i = 0; i <= m; ++i) {if (bt[i] > 0) {if (res == -1 || abs(2 * res - n) > abs(2 * i - n)) {res = i;}}}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<vector<int>> g(n);for (int i = 1; i < n; ++i) {int p;cin >> p;g[p - 1].push_back(i);}auto get = [&](vector<int> &a) -> ll {if ((int)a.size() < 2) {return 0;}int sum = 0, mx = 0;for (int x : a) {sum += x;mx = max(mx, x);}if (mx * 2 >= sum) {return (ll)mx * (sum - mx);}vector<int> b;vector<int> freq(sum + 1);for (int x : a) {freq[x] += 1;}for (int i = 1; i <= sum; ++i) {if (freq[i] > 0) {int d = (freq[i] - 1) / 2;freq[2 * i] += d;freq[i] -= d * 2;for (int j = 0; j < freq[i]; ++j) {b.push_back(i);}}}int x = knapsack(sum, b);return (ll)x * (sum - x);};vector<int> sz(n);ll res = 0;function<void(int)> dfs = [&](int v) {sz[v] = 1;vector<int> a;for (int u : g[v]) {dfs(u);a.push_back(sz[u]);sz[v] += sz[u];}res += get(a);};dfs(0);cout << res << '\n';return 0;
}