【题解】PermuTree (easy version) - Codeforces 1856E1
链接：
https://codeforces.com/contest/1856/problem/E1
题目大意：
给定一棵以节点 \(1\) 为根的树，树的大小不超过 \(n(1\leq n\leq 5000)\) ，给树的节点赋各不相同的权值（可以简化为某个 \([1,n]\) 的排列），使得满足下述条件的节点对 \((u,v)\) 最多： 节点 \(u\) 的权值 \(<\) 节点 \(lca(u,v)\) 的权值 \(<\) 节点 \(v\) 的权值。
解题思路：
从这个计数方式可以想到，两个节点和他们的LCA之间的权值的相对大小才重要，其他的东西不重要。如果这棵树是个二叉树，那么很明显就直接输出中序遍历即可。否则应该把子树们分成左右两个部分，其中左部分的子树的节点的权值均小于LCA的权值，然后右部分的子树的节点的权值均大于LCA的权值，然后容易简化得到，每一棵子树所分配的权值一定是一个连续的整数区间。每一棵子树中，以根节点为LCA的满足条件的节点对的总数，必定刚好等于左部分的子树的节点数乘以右部分的子树的节点数。然后每棵子树内部怎么分配左右，跟外部的树没有任何关系。
习惯上用 \(siz[u]\) 表示节点 \(u\) 的子树的大小，那么可以写为：对每棵子树最大化 \([\sum\limits_{vl\in left} siz_{vl}]\cdot [\sum\limits_{vr\in right} siz_{vr}]\) 。
由于某棵子树内部，所有节点的数量是恒定的，由均值不等式或者二次函数可以知道，左右子树的节点数量总和应该尽可能接近。
那么问题就转化成了：给定一个正整数的集合，将其划分成2个子集，使得两个子集的总和尽可能接近。也就是LeetCode的经典题目。
答案对每个节点为根的子树均求解一次。易知总体的复杂度和某棵子树内的复杂度的上界是一样的。
但是我的确不知道怎么写，去查了下谷歌。
那么这种问题也是按套路使用bitset即可。复杂度为 \(O(n^2/\omega)\) 其中 \(\omega\) 为计算机的字宽，可以大概理解为 \(log\)
对于E2的做法，尝试过用bitset或者直接选/不选，优化，以为卡不到上界，可能我想多了，毕竟是1e6的大杀器，如果是1e5的话应该是可以卡过去的。
看了下红名哥phtniit的答案，正解看起来其实是用NTT做的。想了想的确是有可能。
对于一个长度为n的数组，给定一个正整数的集合，将其划分成2个子集，使得两个子集的总和尽可能接近。上述的bitset算法达到了 \(O(n^2/\omega)\) 的复杂度，然而这个过程居然是可以用NTT进行加速的。想一想也正常，这一类背包问题本身就可以用NTT进行加速。
这类背包问题的重述：有 \(n\) 个物品，每个物品有一个正的重量 \(w_i\) ，求他们互相组合能得到的所有的总重量的列表。
NTT解法：每个物品表示为 \((1 + x^{w_i})\) ，其中 \(x\) 不代表任何东西，其的指数才是关心的部分。 \(1\) 表示不选该物品，也就是 \(0\) 次方代表的 \(0\) 重量， \(x^{w_i})\) 代表选择该物品，会贡献 \({w_i}\) 的重量。
这个二项式的两项分别代表选择或不选择这个物品，然后将这些二项式相乘，得到的就是每个物品选择或不选择的叠加态（怎么看起来有点像量子计算了？）。
对于一个最高次为 \(n\) 的多项式，如果每次暴力乘一个最高次为 \(m\) 的多项式进去，如果用经典的乘法则会是 \(O(n\cdot m)\) 的，所以要引入NTT来加速多项式乘法。
然后对于若干个二项式的合并其实可以使用类似哈夫曼编码的方式进行分治计算，每次选两个长度相近的多项式进行相乘。
分治FNTT计算的总复杂度大概为 \(O(n\cdot log^2n)\) ，而bitset法计算的总复杂度大概为 \(O(n^2/\omega)\) ，要区分在什么数据以上用分治FNTT，什么数据以下用bitset。
由于FNTT的常数比较大，额外奖励它一个常数4，然后用 \(\omega = 32\) 代入计算
得到当 $ \frac{n}{log^2n} \geq 32\cdot 4$ 时才使用FNTT。计算得到n大约是28000左右。但是好像还是跑不过这个数据，可能是常数的差异太大了，这个题可能不允许FNTT通过，这个红名哥其实用了一些trick来加速，也是类似下文说的合并同类物品，因为这里只关心多项式的指数而不关心系数，所以合并的过程中可以忽略系数，只需要管是不是0即可。
看了官方题解之后，知道了二进制优化之后的这个问题是 \(O(n^{1.5}/\omega)\) ，然后FNTT其实就完全没有优势了（因为常数太大）。
namespace FNTT {
const int MOD = 998244353;
const int G = 3;
inline int add (const int &x, const int &y) {
int r = x + y;
if (r >= MOD)
r -= MOD;
return r;
}
inline int sub (const int &x, const int &y) {
int r = x - y;
if (r < 0)
r += MOD;
return r;
}
inline int mul (const int &x, const int &y) {
ll r = (ll) x * y;
if (r >= MOD)
r %= MOD;
return (int) r;
}
int pow (ll x, int n) {
ll res = 1;
while (n) {
if (n & 1)
res = mul (res, x);
x = mul (x, x);
n >>= 1;
}
return res;
}
void FNTT (vector<int>& a, int n, int op) {
for (int i = 1, j = n >> 1, k; i < n - 1; ++i, j += k) {
if (i < j)
swap (a[i], a[j]);
for (k = n >> 1; k <= j; j -= k, k >>= 1);
}
for (int l = 1; (1 << l) <= n; ++l) {
for (int i = 0, Gl = pow (G, (MOD - 1) / (1 << l)); i < n; i += (1 << l)) {
for (int j = i, w = 1; j < i + (1 << (l - 1)); ++j, w = mul (w, Gl)) {
int u = a[j], t = mul (a[j + (1 << (l - 1))], w);
a[j] = add (u, t), a[j + (1 << (l - 1))] = sub (u, t);
}
}
}
if (op == -1) {
reverse (next (a.begin()), a.end());
for (int i = 0, inv = pow (n, MOD - 2); i < n; ++i)
a[i] = mul (a[i], inv);
}
}
void Convolution (vector<int> &A, vector<int> &B) {
int Asize = A.size(), Bsize = B.size(), n;
for (n = 1; n < (Asize + Bsize - 1); n <<= 1);
A.resize (n), B.resize (n);
FNTT (A, n, 1), FNTT (B, n, 1);
for (int i = 0; i < n; ++i) {
A[i] = mul (A[i], B[i]);
}
FNTT (A, n, -1);
A.resize (Asize + Bsize - 1);
for (int &i : A) {
if (i)
i = 1;
}
B.clear();
}
}
const int MAXN = 1000005;
vector<int> vec[MAXN];
priority_queue<pii> vecLen;
void DCFNTT (int n) {
if (n <= 0) {
return;
}
while (!vecLen.empty()) {
vecLen.pop();
}
for (int i = 1; i <= n; ++i) {
vecLen.push ({- (vec[i].size()), i});
}
while (vecLen.size() >= 2) {
int a = vecLen.top().second;
vecLen.pop();
int b = vecLen.top().second;
vecLen.pop();
FNTT::Convolution (vec[a], vec[b]);
vecLen.push ({- (vec[a].size()), a});
}
int x = vecLen.top().second;
vecLen.pop();
swap (vec[1], vec[x]);
}
int n;
vector<int> G[MAXN];
int siz[MAXN];
ll ans;
ll calcBig (int u, const vector<pii> &compressedSizV) {
int n = compressedSizV.size();
for (int i = 1; i <= n; ++i) {
vec[i].clear();
int sizv = compressedSizV[i - 1].first;
int cnt = compressedSizV[i - 1].second;
vec[i].resize (sizv * cnt + 1);
for (int j = 0; j <= cnt; ++j) {
vec[i][j * sizv] = 1; // 此处忽略系数
}
}
DCFNTT (n);
int sumSizV = siz[u] - 1;
if (sumSizV >= 2) {
int leftSiz = 0;
for (int i = 0; i <= sumSizV; ++i) {
if (vec[1][sumSizV / 2 - i]) {
leftSiz = sumSizV / 2 - i;
break;
}
if (vec[1][sumSizV / 2 + i]) {
leftSiz = sumSizV / 2 + i;
break;
}
}
return 1LL * leftSiz * (sumSizV - leftSiz);
}
return 0LL;
}
const int MID = 200000;
template<int BITLEN = 1>
ll calcSmall (int u, const vector<pii> &compressedSizV) {
int sumSizV = siz[u] - 1;
if (sumSizV >= BITLEN) {
return calcSmall<min (BITLEN * 2, MAXN) > (u, compressedSizV);
}
vector<int> items;
for (auto [sizv, cnt] : compressedSizV) {
// 二进制优化01背包
int p2 = 1;
while (p2 <= cnt) {
items.push_back (sizv * p2);
cnt -= p2;
p2 *= 2;
}
items.push_back (sizv * cnt);
}
bitset<BITLEN> canform = 0;
canform[0] = 1;
for (int &item : items) {
canform = (canform << item) | canform;
}
if (sumSizV >= 2) {
int leftSiz = 0;
for (int i = 0; i <= sumSizV; ++i) {
if (canform[sumSizV / 2 - i]) {
leftSiz = sumSizV / 2 - i;
break;
}
if (canform[sumSizV / 2 + i]) {
leftSiz = sumSizV / 2 + i;
break;
}
}
return 1LL * leftSiz * (sumSizV - leftSiz);
}
return 0LL;
}
void dfs (int u) {
siz[u] = 1;
for (int &v : G[u]) {
dfs (v);
siz[u] += siz[v];
}
if (siz[u] <= 1) {
return;
}
map<int, int> compressedSizV;
for (int &v : G[u]) {
compressedSizV[siz[v]]++;
}
int maxSizV = compressedSizV.rbegin()->first;
int sumSizV = siz[u] - 1;
if (maxSizV * 2 >= sumSizV) {
ans += 1LL * maxSizV * (sumSizV - maxSizV);
} else if (sumSizV < MID) {
ans += calcSmall (u, vector<pii> (compressedSizV.begin(), compressedSizV.end()));
} else {
ans += calcBig (u, vector<pii> (compressedSizV.begin(), compressedSizV.end()));
}
}
void solve() {
RD (n);
ans = 0;
for (int i = 1; i <= n; ++i) {
G[i].clear();
}
for (int i = 2; i <= n; ++i) {
int p;
RD (p);
G[p].push_back (i);
}
dfs (1);
WT (ans);
}
但是Heltion那个是什么算法呢？ https://codeforces.com/contest/1856/submission/217331135 （其实是类似官方题解的做法。）
或者去看官方题解吧，这个背包算法居然是有一个 \(O(n^{1.5}/\omega)\) 的做法？
官方题解的做法是一个二进制分组背包去除重复元素的解法。但是复杂度是不知道怎么证明的？由等差数列求和或者 \(1+2+3...+O(sqrt(n)) \geq n\) ，所以二进制分组之后，压缩了相同的元素出现的次数，把原本的至多 \(n\) 个物品缩减到了 \(\sqrt{n}\) 个。这个是很好理解的，因为所有的元素加起来恰好等于 \(n\) ，而把每个重复的元素按二进制压缩之后，原本的 \(k\) 个重复的元素被压缩成 \(log2(k)\) 个，而不能被压缩数量的最小值为 \(1\) 个，为了搞坏复杂度要物品数尽量多，所以宁愿创造一个新的元素也不能创造一个重复的元素。（比如现在有压缩的 1个1，2个1，4个1，如果想再多一个元素，那么是花费8个代价创造一个新的元素是8个1，不如花费2个代价创造一个2）。
int resti = cnt[i];
for (int p2 = 1; p2 <= resti; p2 <<= 1) {
items.push_back (w[i]*p2);
resti -= p2;
}
if (resti) {
items.push_back (w[i]*resti);
}
这道题我愿称之为背包之王。
这里值得学习的其实是关于使用template来自动控制bitset的做法，如下文，用min限制了MAXLEN长度之后，template就能自动生成一系列函数了。注意是32位的编译器加上默认32位的bitset跑得最快。
template<int BITSETLEN = 32>
int templateBitset (int len) {
if (len >= BITSETLEN) {
return templateBitset<min (BITSETLEN * 2, MAXLEN) > (len);
}
bitset<BITSETLEN> b;
return 0;
}
这里有一点就是二进制分组背包的实现方式，一定要从1,2,4,8开始分，剩下的另外分一堆。
const int MAXN = 1000005;
int n;
int siz[MAXN];
vector<int> G[MAXN];
ll ans;
template<int BITLEN = 64>
ll calcSmall (int u, int maxSizV, int* cntSiz) {
int sumSizV = siz[u] - 1;
if (sumSizV >= BITLEN) {
return calcSmall<min (BITLEN * 2, MAXN) > (u, maxSizV, cntSiz);
}
vector<int> items;
for (int i = 0; i <= maxSizV; ++i) {
// 二进制优化01背包
if (cntSiz[i]) {
int cnt = cntSiz[i];
int p2 = 1;
while (p2 <= cnt) {
items.push_back (i * p2);
cnt -= p2;
p2 *= 2;
}
items.push_back (i * cnt);
}
}
bitset<BITLEN> canform = 0;
canform[0] = 1;
for (int &item : items) {
canform |= canform << item;
}
if (sumSizV >= 2) {
int leftSiz = 0;
for (int i = 0; i <= sumSizV; ++i) {
if (canform[sumSizV / 2 - i]) {
leftSiz = sumSizV / 2 - i;
break;
}
if (canform[sumSizV / 2 + i]) {
leftSiz = sumSizV / 2 + i;
break;
}
}
return 1LL * leftSiz * (sumSizV - leftSiz);
}
return 0LL;
}
void dfs (int u) {
siz[u] = 1;
int maxSizV = 0;
for (int &v : G[u]) {
dfs (v);
siz[u] += siz[v];
cmax (maxSizV, siz[v]);
}
if (siz[u] <= 2) {
return;
}
int sumSizV = siz[u] - 1;
if (maxSizV * 2 >= sumSizV) {
ans += 1LL * maxSizV * (sumSizV - maxSizV);
return;
}
static int cntSiz[MAXN];
for (int i = 0; i <= maxSizV; ++i) {
cntSiz[i] = 0;
}
for (int &v : G[u]) {
++cntSiz[siz[v]];
}
vector<pii> compressedSizV;
for (int i = 0; i <= maxSizV; ++i) {
if (cntSiz[i]) {
compressedSizV.push_back ({i, cntSiz[i]});
}
}
ans += calcSmall (u, maxSizV, cntSiz);
return;
}
void solve() {
RD (n);
ans = 0;
for (int i = 1; i <= n; ++i) {
G[i].clear();
}
for (int i = 2; i <= n; ++i) {
int p;
RD (p);
G[p].push_back (i);
}
dfs (1);
WT (ans);
}
这个是560ms的代码，确实是不错了。模板化生成bitset的代码是必须要加的，不然小数据会直接T掉。
通过这道题，学习了模板化bitset、二进制分组背包的写法、使用NTT解决01背包问题。收获真是不一般地大呢。
由此，\(n\) 个物品 \(w_i\) 的01背包组合出某个重量，有：
\(O(2^n)\) 的暴力枚举每个物品拿or不拿。
\(O(n\cdot \sum w_i)\) 的dp枚举每个重量是否能被组成。
\(O(n \frac {\sum w_i}{\omega})\) 的bitset优化。
\(O(n log^2n)\) 的分治FFT/NTT做法（可顺带求出能组合成的方法数，此时不便使用二进制分组优化，除非先算出组合数）。
以及将上述的 \(n\) 压缩为至多 \(\sqrt{n}\) 个物品的二进制分组优化。