首页 > 其他分享 >HZOI 大根堆 线段树合并

HZOI 大根堆 线段树合并

时间:2023-06-09 09:00:11浏览次数:39  
标签:大根堆 limits 线段 样例 HZOI sum 节点 size

题目描述
给定一棵n个节点的有根树,编号依次为1到n,其中1号点为根节点。每个点有一个权值v_i。

你需要将这棵树转化成一个大根堆。确切地说,你需要选择尽可能多的节点,满足大根堆的性质:对于任意两个点i,j,如果i在树上是j的祖先,那么v_i>v_j。

请计算可选的最多的点数,注意这些点不必形成这棵树的一个连通子树。

输入格式
第一行包含一个正整数n(1<=n<=200000),表示节点的个数。

接下来n行,每行两个整数v_i,p_i(0<=v_i<=10^9,1<=p_i<i,p_1=0),表示每个节点的权值与父亲。

输出格式
输出一行一个正整数,即最多的点数。

样例
样例输入
6
3 0
1 1
2 1
3 1
4 1
5 1
样例输出
5


私货:
摆了,有时间在详细写。
思路历程:
1.最开始想最暴力的方法,我先把树建出来,然后对每一个点固定为树根,我暴力搜它的子树,pushup再pushup,存进去我的数组,赢!
今天你赢赢赢,明天我输光光
但是专题的名字叫线段树合并啊
2.或许dp可以解决这个问题,我还是固定一个点作为树根,但是我用\(f_u,_i\)表示以u为树根的子树里的节点权值小于i的个数。\(i\)<=\(v_u\).
我们用\(size_u\)表示u的子节点大小。
就有了转移方程:
………………
………………
推出来了吗?
我没推出来呢()
欸要不你悄悄把转移方程洛谷V我,要不然这个博客就结束了()
…………
ok现在我们得到了转移方程,(感\(K_8He\)老师的博客对这个fw的大力支持)
\(1....\)\(f_u,_i=\sum\limits_{size_u}^{}\) \(f_u,_i\) , \(i<=v_u\)
\(2....\)\(f_u,_i=max(\sum\limits_{size_u}^{}f_u,_i,\sum\limits_{size_u}^{}\) \(f_u,_{i+1}\)-1) , \(i>=v_u\)

贴贴(链接)
ps:没有贴错人也没有贴错题,详见下()
再贴
ok现在不会了去看题解了拜拜
先这样吧一会在写代码,我转移方程应该是错的()回来再改

标签:大根堆,limits,线段,样例,HZOI,sum,节点,size
From: https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/17468174.html

相关文章

  • 线段树合并学习笔记
    前言我是一个什么什么傻卵啊啊啊啊啊啊啊啊,连线段树合并都学不明白qaq正文权值线段树含义:是用来维护好多好多桶的线段树.桶是一个用来计数的东西.与普通线段树的区别普通线段树是用来维护区间和、积、最值等一系列的东西.权值线段树是用来维护某个区间内的数出现了......
  • 题解 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
    传送门如题目所言,这就是个线段树合并的板子题。题目大意题目描述首先村落里的一共有\(n\)座房屋,并形成一个树状结构。然后救济粮分\(m\)次发放,每次选择两个房屋\((x,y)\),然后对于\(x\)到\(y\)的路径上(含\(x\)和\(y\))每座房子里发放一袋\(z\)类型的救济粮。然......
  • Luogu P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
    [Vani有约会]雨天的尾巴/【模板】线段树合并题目背景深绘里一直很讨厌雨天。灼热的天气穿透了前半个夏天,后来一场大雨和随之而来的洪水,浇灭了一切。虽然深绘里家乡的小村落对洪水有着顽固的抵抗力,但也倒了几座老房子,几棵老树被连根拔起,以及田地里的粮食被弄得一片狼藉。无奈......
  • Codeforces 1566G - Four Vertices(线段树分治)
    交了整整2页,本来想用随机化卡过去的,后来发现我的实现跑得太慢就写正常做法了。首先发现最优答案对应的四个点只可能有以下两种可能:\(a,b\)间有边,\(c,d\)间有边,此时答案是\(a,b\)边权值加\(c,d\)边权值。\(a\)与\(b,c,d\)三个点间都有边,此时答案是三条边权值之和。......
  • 「学习笔记」线段树
    介绍:线段树是一棵二叉搜索树,思想与分治很想,把一段区间平分平分再平分,平分到不能平分为止,可以进行方便的区间修改和区间查询,当然,树状数组能做的单点修改、单点查询,线段树也可以更好地实现,总之,线段树是树状数组的升级版,此外,线段树能做的平衡树也能做,但平衡树码量太大,考场上一般写......
  • 线段树模板题
    目录洛谷3372线段树区间加法/区间求和洛谷3373线段树区间加法/区间乘法/区间求和.洛谷3372线段树区间加法/区间求和//byDTTTTTTT2023/6/2//Luogu3372#include<iostream>#definelllonglong#definelc(p<<1)#definerc(p<<1|1)usingnamespacestd;constint......
  • Codeforces 1515I - Phoenix and Diamonds(值域倍增+线段树)
    首先\(c\)很大,因此复杂度跟\(c\)有关的项肯定只能是\(\logc\)之类的。类比IOI2021dungeons的套路,我们对值域进行分层,假设\(c\in[2^{\omega-1},2^{\omega})\),考虑令重量在\(\ge2^{\omega-1}\)的物品为“重物品”,其他物品为“轻物品”,那么一个显然的性质是我们最多只......
  • CF101234A Hacker Cups and Balls【二分+线段树】
    Description给一个长度为n的排列,对它做m次操作,每次对[l,r]区间内进行升序/降序排序。问最后的序列处于最中心的数是多少(n为奇数)。Solution是一类没有写过的题,参考题解。二分答案,对于当前的mid,将大于等于mid的数设置为1,小于mid的数设置为0。这样一来,叶结点的值......
  • 【数据结构】吉司机线段树
    【数据结构】吉司机线段树(SegmentTreeBeats)吉司机线段树,是由杭州学军中学的吉如一在2016年国集论文当中提出的,解决了区间最值操作和区间历史最值问题。题目描述给出一个长度为\(n\)的数列\(A\),同时定义一个辅助数组\(B\),\(B\)开始与\(A\)完全相同。接下来进行了\(m......
  • POJ1151(线段树+扫描线求矩形面积并)
    题目:http://poj.org/problem?id=1151 #include<iostream>#include<string.h>#include<algorithm>#include<stdio.h>usingnamespacestd;constintN=10005;structnode{intl,r;intcov;doublelen;};structline{......