BZOJ 5499.「十二省联考 2019」春节十二响

略有思维难度,其实挺好写的。

首先,考虑一条链的情况。
那么根节点最多有两个儿子,分别延伸出两条链。
当且仅当在这两条链中各选择一个点(除了根节点),才不会有祖孙关系。
所以可以贪心地上两个堆。

考虑 100%100\% 的数据,那么这个时候就涉及到堆的合并。
于是我们启发式合并。

这个时候,时间复杂度不再是 O(nlog2n)O(n \log^2 n) 了。
因为合并的时候,更大的那个,大小应该是其对应子树中的最长链长度。
根据长链剖分的分析,得到 O(nlogn)O(n \log n)

还有,
pbds 天 下 第 一!

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int N = 2e5;
int n,a[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
long long ans;
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
__gnu_pbds::priority_queue<int> q[N + 5];
int id[N + 5];
int merge(int x,int y)
{
static int buf[N + 5];
if(q[id[x]].size() < q[id[y]].size())
swap(id[x],id[y]);
int m = q[id[y]].size();
for(register int i = 1;i <= m;++i)
buf[i] = max(q[id[x]].top(),q[id[y]].top()),q[id[x]].pop(),q[id[y]].pop();
for(register int i = 1;i <= m;++i)
q[id[x]].push(buf[i]);
return id[x];
}
void dfs(int p,int fa)
{
static int tot = 0;
id[p] = ++tot;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa)
dfs(to[i],p),id[p] = merge(p,to[i]);
q[id[p]].push(a[p]);
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
int u;
for(register int i = 2;i <= n;++i)
scanf("%d",&u),add(u,i);
dfs(1,0);
for(;!q[id[1]].empty();q[id[1]].pop())
ans += q[id[1]].top();
printf("%lld\n",ans);
}