春节十二响

题目背景
「清明时节雨纷纷，路上行人欲断魂。」

2075 年的清明没有春雨。在漫天飞雪的笼罩下，穿行在冰原间的，只有载着人类微薄希望的雪地车。

遥遥 4.22 光年的征途，对于地球这孤独的旅人而言，恐怕也是无比寂寞的吧。

题目描述
距离苏拉威西只有一百公里了，车内的空气比窗外更加冰冷。四双眼睛紧盯着艾莉芬面前的屏幕，那是控制行星发动机的关键程序：春节十二响。他需要将其部署到电力控制系统的一个芯片中。

「春节十二响」由 $n$ 个子程序构成，第 $i$ 个子程序所需的内存空间是 $M_i$。这 $n$ 个子程序之间的调用关系构成了一棵以第 $1$ 个子程序为根的树，其中第 $i$ 个子程序在调用树上的父亲是第 $f_i$ 个子程序。

由于内存紧张，电力控制芯片上提供了一种内存分段机制。你可以将内存分为若干个段 $S_1, S_2, dots, S_k$，并将每个程序预先分配到一个固定的段。如果两个子程序没有直接或间接的调用关系，则他们可以被分配到同一个段中，反之则不能。换言之，当且仅当 $a$ 和 $b$ 在调用树上**不是祖先-后代关系**，$a$ 和 $b$ 可以被分配到同一个段中。

一个段的大小应当是所有分配到这个段的子程序所需内存大小的最大值，所有段大小的和不能超过系统的内存大小。

现在艾莉芬想要知道，电力控制芯片至少要有多少内存，才能保证春节十二响的正确运行。即：最少需要多大的内存，才能通过先**将内存分成若干个段**，再**把每个子程序分配到一个段中**，使得**每个段中分配的所有子程序之间不存在祖先-后代关系**。

sol

可以发现如果分成的段数最少那么答案最优。

一棵深度为dep的树只要要分dep层。

现在考虑怎么合并两棵树：两个大根堆，每次取较大的堆顶，直到有个堆为空。

类似启发式合并。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 200005
 9 using namespace std;
10 int n,a[maxn],f[maxn],t[maxn],tp;
11 priority_queue<int>q[maxn];
12 int main(){
13     cin>>n;
14     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
15     for(int i=2;i<=n;i++)scanf("%d",&f[i]);
16     for(int i=n;i>1;i--){
17         int x=i,y=f[i];    q[x].push(a[i]);
18         if(q[x].size()>q[y].size())swap(q[x],q[y]);
19         for(tp=0;!q[x].empty();q[x].pop(),q[y].pop())t[++tp]=max(q[x].top(),q[y].top());
20         for(int j=1;j<=tp;j++)q[y].push(t[j]);
21     
22     }
23     long long ans=a[1];
24     for(;!q[1].empty();q[1].pop())ans+=q[1].top();
25     cout<<ans<<endl;
26     return 0;
27 }

View Code