[loj3052]春节十二响
2024-09-04 21:53:23
首先可以发现对于两条链来说,显然是对两边都排好序,然后大的配大的,小的配小的(正确性比较显然),最后再加入根(根只能单独选)
这个结果其实也可以理解为将所有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 }
最新文章
- POI
- Centos搭建Linux测试环境,几个基本的设置项
- nohup不输出日志信息的方法,及linux重定向学习
- telnet localhost 8089 ==》》命令使用
- phalcon框架学习之view
- Grid分组特性
- 2015.1写留言板的时用的 知识点和函数 --->;总结
- ";position:relative";在IE中的Bug
- 字符串匹配算法-BM
- Centos yum install
- Long,String类型的两个值进行比较,注意点!!!
- 浏览器检测JS代码(兼容目前各大主流浏览器)
- android 设置头像以及裁剪功能
- 自定义浏览器滚动条的样式,打造属于你的滚动条风格——兼容IE和webkit(ff不支持)
- centos文件权限详解
- Struts 之 通配符 路径匹配 常量用法 配置默认值
- 理解Java的NIO
- python工具 - 批量文件重命名
- Codeforces 977F - Consecutive Subsequence - [map优化DP]
- OpenCV——基本图形绘制(椭圆、圆、多边形、直线、矩形)