题目地址：P5290 [十二省联考2019]春节十二响
骗分方法
如果你实在一点思路也没有，暴力都不会打，那么请考虑一下骗分。
方法一
输出所有 \(M\) 的和。
期望得分：0分。
方法二
注意到有 \(15\) 分为一条链，分两种情况考虑：
- 1号点有一个儿子——详见方法一。
- 1号点有两个儿子——把对这两个儿子下的两条链弄成两个堆，每次取出两个堆的堆顶，取 \(max\) 加入答案，当一个堆取尽后，把另一个堆里的所有元素加入答案，最后加入 \(M_1\) 。
期望得分：15分。
暴力方法
如果你的暴力时间复杂度很低并且常数很优秀，那么拿到一道题的大部分分数是很容易的。
方法三
可以写一个很高超的纯暴搜过掉数据较小的2~4个点。
时间复杂度：不详。
期望得分：10~20分。
方法四
如果两个点是祖先后代关系，则在这两点之间连边，最终会形成一个 \(n\) 个点的图。则答案是这个图的一个最大独立集。
图的最大独立集是 NPC 问题，最快的方法貌似是状压， \(O(3^n)\) 。
期望得分：45分。
方法五
借用方法四的思想，如果 \(x,y\) 是祖先后代关系，则 \(a_{x,y}\) 为 \(1\) ，否则为 \(0\) ，这样可以构造出来一个 \(n \times n\) 的 01 矩阵。
按 \(M\) 值从大到小贪心地选。每选择一个就再从大到小把能选的都选上，然后把选择的这个的 \(M\) 值加入答案。
由于每次选完之后都要更新可选的集合，这个更新是 \(O(n)\) 的，而每次选择一个之后，还有要从大到小把能选的都选上，这个过程也是 \(O(n)\) 的，一共要进行 \(O(n)\) 次选择，所以总时间复杂度为 \(O(n^3)\) 的。
期望得分：45分。
方法六
从方法四的 \(O(3^n)\) 到方法五 \(O(n^3)\) ，期望得分没变海星。
考虑优化方法五，我们在方法五中看到这两个词：01 矩阵，集合。尝试用 bitset 优化，时间复杂度严格来讲没变，但是常数变成原来的 \(\frac{1}{64}\) 。
期望得分：60分。
方法七
换一种思路。
考虑类似方法二的第 \(2\) 种情况合并两颗子树。
时间复杂度： \(O(n^2)\) 。
期望得分：60分。
考场代码
我在考场上写出来的代码是方法六和方法二的结合版，得分为 \(75\) 分。
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const int N = 2e5 + 6;
int n, a[N], f[N];
ll ans = 0;
inline int rd() {
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + (ch - '0'), ch = getchar();
return x;
}
inline bool pd1() {
for (int i = 2; i <= n; i++) if (f[i] != i - 1) return 0;
return 1;
}
inline void P101112_1() {
for (int i = 1; i <= n; i++) ans += a[i];
cout << ans << endl;
}
namespace P101112_2 {
int deg[N];
inline bool pd() {
for (int i = 2; i <= n; i++) ++deg[f[i]];
if (deg[1] != 2) return 0;
for (int i = 2; i <= n; i++) if (deg[i] > 1) return 0;
return 1;
}
int son[N];
priority_queue<int> q[2];
inline void work() {
int g[2], t = 0;
for (int i = 2; i <= n; i++)
if (f[i] == 1) g[t++] = i;
else son[f[i]] = i;
ans = a[1];
for (int i = 0; i < 2; i++) {
int x = g[i];
while (x) q[i].push(a[x]), x = son[x];
}
while (q[0].size() && q[1].size())
ans += max(q[0].top(), q[1].top()), q[0].pop(), q[1].pop();
for (int i = 0; i < 2; i++)
if (q[i].size())
while (q[i].size()) ans += q[i].top(), q[i].pop();
cout << ans << endl;
}
}
namespace TX {
const int M = 2e3 + 6;
bitset<M> b[M], o, v;
vector<int> e[M];
int st[M], top = 0, p[M];
pii g[M];
void dfs(int x) {
b[p[x]] = o;
for (int i = 1; i <= top; i++) b[p[st[i]]][p[x]] = 0;
st[++top] = x;
o[p[x]] = 0;
for (unsigned int i = 0; i < e[x].size(); i++) {
int y = e[x][i];
if (!o[p[y]]) continue;
dfs(y);
}
o[p[x]] = 1;
--top;
}
inline void work() {
for (int i = 2; i <= n; i++) e[f[i]].push_back(i);
for (int i = 1; i <= n; i++) g[i] = mp(a[i], i);
sort(g + 1, g + n + 1);
for (int i = 1; i <= n; i++) p[g[i].second] = i;
o.set();
dfs(1);
v.reset();
for (int i = n; i; i--) {
if (v[i]) continue;
o = b[i];
ans += g[i].first;
v[i] = 1;
for (int j = i - 1; j; j--)
if (o[j] && !v[j]) {
v[j] = 1;
o &= b[j];
}
}
cout << ans << endl;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) a[i] = rd();
for (int i = 2; i <= n; i++) f[i] = rd();
if (pd1()) {
P101112_1();
return 0;
}
if (P101112_2::pd()) {
P101112_2::work();
return 0;
}
if (n < 2001) {
TX::work();
return 0;
}
return 0;
}正确方法
方法八
方法七是 \(O(n^2)\) 的，思考瓶颈在哪儿？
合并两颗子树 \(x,y\) 时，我们相当于进行了 \(O(max(size_x,size_y))\) 。
能否将复杂度降到 \(O(min(size_x,size_y))\) ？
先考虑降复杂度之后，总的时间复杂度是多少？
降复杂度之后，相当于每一次合并，用 \(O(min(size_x,size_y))\) 扔掉了 \(min(size_x,size_y)\) 个元素。换句话说，扔掉一个元素是 \(O(1)\) 的。我们要把 \(n\) 个元素经过若干次合并，扔掉 \(O(n)\) 个元素，最终剩下 \(1\) 个元素。那么扔元素的复杂度为 \(O(n)\) ，考虑堆的影响，总时间复杂度为 \(O(n\ log\ n)\) 。
时间复杂度满足限制，可以放心的回去考虑如何降复杂度了。
当我们取完 \(min(size_x,size_y)\) 个元素后，一个堆是空的，另一个堆还剩下一些元素。
那我们直接把刚才取出来的元素再塞到非空的那个堆中不就完了么？
我再告诉你，这个正解还有个好听的名字：启发式合并。
代码实现细节
有一个小细节是，代码实现中会出现 swap 两个堆的情况。
在 ouuan 的博客十二省联考2019 游记 & 题解中，对此有这样的说法：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 6;
int n, a[N], f;
vector<int> e[N], o;
priority_queue<int> q[N];
inline void merge(int x, int y) {
if (q[x].size() < q[y].size()) swap(q[x], q[y]);
while (q[y].size()) {
o.push_back(max(q[x].top(), q[y].top()));
q[x].pop(), q[y].pop();
}
while (o.size()) q[x].push(o.back()), o.pop_back();
}
void dfs(int x) {
for (unsigned int i = 0; i < e[x].size(); i++)
dfs(e[x][i]), merge(x, e[x][i]);
q[x].push(a[x]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 2; i <= n; i++) scanf("%d", &f), e[f].push_back(i);
dfs(1);
long long ans = 0;
while (q[1].size()) ans += q[1].top(), q[1].pop();
cout << ans << endl;
return 0;
}