目录
显示
题目链接
https://www.luogu.org/problem/P5290
题解
我们从一条链的特殊数据下手。
注意到 \(1\) 号点不一定是链的一端，这就意味着 \(1\) 号点可能会最多有两个子树，而这两个子树又都是一条链。
我们可以采用这样的贪心策略：首先将 \(1\) 号点单独分为一段（\(1\) 号点不能和其他点同时在一个段中）。接下来对每个链分别维护一个大根堆，每次取出两个堆中的最大值分成一段，并分别弹出两个堆的堆顶，直到其中一个堆空为止。
剩下一个堆中的任意两个元素都不能同时在一个段中，我们对每个元素新开一个段即可。
接下来将问题扩展到一般的树。
类似上面的方法，我们对每个节点维护一个堆。刚开始时，每个堆里只有该节点的值。
接下来从根节点开始进行 dfs。
每次遍历完一个子树后，我们就将当前节点与子节点的堆进行一轮合并：弹出两个堆的堆顶，并将两者最大值加入新堆即可。一个堆空的时候，就把另一个堆的剩余元素全部加入新堆。
怎么合并效率最高呢？启发式合并！将小的堆合并到大的堆就可以了。
该算法的复杂度是多少呢？因为每个点最多只会弹出一次，时间复杂度是 \(O(n \log n)\) 的。（具体可以参考 Topcarry 的题解）
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct edge
{
int v,next;
}e[200005];
int head[200005],m[200005],cnt;
priority_queue<int> q[200005];
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void merge(int x,int y)
{
if(q[x].size()<q[y].size())swap(q[x],q[y]);
priority_queue<int> tmp;
while(!q[y].empty())
{
tmp.push(max(q[x].top(),q[y].top()));
q[x].pop(),q[y].pop();
}
while(!tmp.empty())
{
q[x].push(tmp.top());
tmp.pop();
}
}
void dfs(int u)
{
for(int i=head[u];i;i=e[i].next)
dfs(e[i].v),merge(u,e[i].v);
q[u].push(m[u]);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>m[i];
for(int i=2;i<=n;i++)
{
int f;
cin>>f;
addedge(f,i);
}
dfs(1);
long long ans=0;
while(!q[1].empty())
ans+=q[1].top(),q[1].pop();
cout<<ans<<endl;
return 0;
}