首先可以发现对于两条链来说,显然是对两边都排好序,然后大的配大的,小的配小的(正确性比较显然),最后再加入根(根只能单独选)
这个结果其实也可以理解为将所有max构成一条新的链,求出
因此,对于每一个结点计算出答案,然后与别的点合并得到父亲,用启发式合并+set时间复杂度为两个log。

 1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 struct ji{
5 int nex,to;
6 }edge[N];
7 priority_queue<int>qq,q[N];
8 int E,n,x,y,a[N],f[N],head[N];
9 long long ans;
10 void add(int x,int y){
11 edge[E].nex=head[x];
12 edge[E].to=y;
13 head[x]=E++;
14 }
15 int top(priority_queue<int>&q){
16 int k=q.top();
17 q.pop();
18 return k;
19 }
20 void dfs(int k){
21 for(int i=head[k];i!=-1;i=edge[i].nex){
22 int v=edge[i].to;
23 dfs(v);
24 if (q[f[k]].size()<q[f[v]].size())swap(f[k],f[v]);
25 while (!q[f[v]].empty())
26 qq.push(max(top(q[f[k]]),top(q[f[v]])));
27 while (!qq.empty())q[f[k]].push(top(qq));
28 }
29 q[f[k]].push(a[k]);
30 }
31 int main(){
32 scanf("%d",&n);
33 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
34 for(int i=1;i<=n;i++)f[i]=i;
35 memset(head,-1,sizeof(head));
36 for(int i=2;i<=n;i++){
37 scanf("%d",&x);
38 add(x,i);
39 }
40 dfs(1);
41 while (!q[f[1]].empty())ans+=top(q[f[1]]);
42 printf("%lld",ans);
43 }

最新文章

  1. POI
  2. Centos搭建Linux测试环境,几个基本的设置项
  3. nohup不输出日志信息的方法,及linux重定向学习
  4. telnet localhost 8089 ==》》命令使用
  5. phalcon框架学习之view
  6. Grid分组特性
  7. 2015.1写留言板的时用的 知识点和函数 ---&gt;总结
  8. &quot;position:relative&quot;在IE中的Bug
  9. 字符串匹配算法-BM
  10. Centos yum install
  11. Long,String类型的两个值进行比较,注意点!!!
  12. 浏览器检测JS代码(兼容目前各大主流浏览器)
  13. android 设置头像以及裁剪功能
  14. 自定义浏览器滚动条的样式,打造属于你的滚动条风格——兼容IE和webkit(ff不支持)
  15. centos文件权限详解
  16. Struts 之 通配符 路径匹配 常量用法 配置默认值
  17. 理解Java的NIO
  18. python工具 - 批量文件重命名
  19. Codeforces 977F - Consecutive Subsequence - [map优化DP]
  20. OpenCV——基本图形绘制(椭圆、圆、多边形、直线、矩形)

热门文章

  1. 如何基于Jupyter notebook搭建Spark集群开发环境
  2. 手机淘宝轻店业务 Serverless 研发模式升级实践
  3. java课堂测试3第一部分(未完善)
  4. 洛谷3203 弹飞绵羊(LCT)
  5. 基于TLS证书手动部署kubernetes集群
  6. 2020.10.17-pta天梯练习赛补题
  7. easyDialog 简单、实用的弹出层组件
  8. javascript-vue介绍
  9. Android构建工具--AAPT2源码解析(一)
  10. airtest常用指令