春节十二响

春节十二响
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说春节十二响,希望能够帮助大家进步!!!

省选Day2T2

自己的思路:
将树上所有的链存到好几个数组里,每次取出每个数组的最大值比较,将最大的计入答案。其实很接近正解了。

.

正解:将每个点的子树合成一个堆,启发式合并(由小到大)。
上代码吧

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #define LL long long using namespace std; const int N = 200000+10; int n,a[N],fa[N],tmp[N],id[N],tim; int head[N],tot; struct edge{ int node,next; }e[N]; priority_queue<int> q[N]; inline int read() { register int x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return (f==1)?x:-x; } void add(int x,int y) { e[++tot].next=head[x]; head[x]=tot; e[tot].node=y; } void dfs(int x) { id[x]=++tim; for(int i=head[x];i;i=e[i].next) { int v=e[i].node; dfs(v); if(q[id[x]].size()<q[id[v]].size()) swap(id[x],id[v]); int m=q[id[v]].size(); for(int i=1;i<=m;i++) { tmp[i]=max(q[id[x]].top(),q[id[v]].top()); q[id[x]].pop(); q[id[v]].pop(); } for(int i=1;i<=m;i++) q[id[x]].push(tmp[i]); } q[id[x]].push(a[x]); } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=2;i<=n;i++) fa[i]=read(),add(fa[i],i); dfs(1); LL ans=0; while(!q[id[1]].empty()) ans+=q[id[1]].top(),q[id[1]].pop(); printf("%lld\n",ans); return 0; }

转载于:https://www.cnblogs.com/karryW/p/10806885.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29855

发表评论