[洛谷 5290,loj 3052][十二省联考2019]春节十二响

题目链接

https://www.luogu.org/problem/P5290

https://loj.ac/problem/3052

题解

我们从一条链的特殊数据下手。

注意到 \(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;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注