站长工具大全,湛江有没有做网站的,宣城哪里做网站,自考网页设计素材题意
传送门 Codeforces 1856E2 PermuTree (hard version)
题解
可以独立考虑每一个固定的 p l c a ( u , v ) plca(u,v) plca(u,v) 对答案的贡献。可以观察到#xff0c;对于 p p p 的每一棵子树#xff0c;其所有节点在最优情况下仅有 a p a v a_p a_v ap…题意
传送门 Codeforces 1856E2 PermuTree (hard version)
题解
可以独立考虑每一个固定的 p l c a ( u , v ) plca(u,v) plca(u,v) 对答案的贡献。可以观察到对于 p p p 的每一棵子树其所有节点在最优情况下仅有 a p a v a_p a_v apav 或 a p a v a_p a_v apav 两种可能。那么需要在值域上将子树的节点左右划分那么需要求解所有子树的子集中子树规模 s z v sz_v szv 的和最接近所有子树和的 1 / 2 1/2 1/2 的值 x x x则对答案的贡献为 x ∗ ( s z p − 1 − x ) x * (sz_p - 1 - x) x∗(szp−1−x)。对于上述背包问题满足 s z u ⋯ s z v s z p − 1 sz_u \cdots sz_v sz_p - 1 szu⋯szvszp−1可以做到 O ( s z p s z p ) O(sz_p\sqrt{sz_p}) O(szpszp )具体做法类似于二进制拆分不断将相同的值合并最终每一个不同的值仅有常数个则不同的值数量为 O ( s z p ) O(\sqrt{sz_p}) O(szp )。
若存在 s z v ∗ 2 ≥ s z p − 1 sz_v * 2 \geq sz_p - 1 szv∗2≥szp−1则无需进行背包。考虑最坏情况即平衡的多叉树容易观察到所有背包 DP 的复杂度为 O ( n n ) O(n\sqrt{n}) O(nn ) 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, vectorint b) {if (m n) {return knapsackmin(m * 2, N)(n, b);}bitsetm 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;vectorvectorint g(n);for (int i 1; i n; i) {int p;cin p;g[p - 1].push_back(i);}auto get [](vectorint 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);}vectorint b;vectorint 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);};vectorint sz(n);ll res 0;functionvoid(int) dfs [](int v) {sz[v] 1;vectorint 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;
}
