给定一棵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
输出一行一个正整数，即最多的点数。
样例输入
6
3 0
1 1
2 1
3 1
4 1
5 1
样例输出
5
查看代码
#include
#include
#include
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 1;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 0;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return x;
else return -x;
}
const int N = 2e5;
#define ls(x) t[x].ls
#define rs(x) t[x].rs
struct node{
int ls,rs,sum;
}t[N << 2];//每个节点独立存在不需要pushup
int to[N],head[N],nxt[N],cnt;
int lsh[N],f[N],v[N];
int M,tot;
inline void add(int u,int v){
to[++cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
}
void update(int &rt,int l,int r,int L,int R){
if(!rt) rt = ++tot;
if(L <= l && r <= R){
t[rt].sum++;
return;
}
int mid = (l + r) >> 1;
if(L <= mid) update(ls(rt),l,mid,L,R);
if(mid < R) update(rs(rt),mid+1,r,L,R);
}
int merge(int ra,int rb,int l,int r){
if(!ra || !rb) return ra + rb;
t[ra].sum += t[rb].sum;
int mid = (l + r) >> 1;
ls(ra) = merge(ls(ra),ls(rb),l,mid);
rs(ra) = merge(rs(ra),rs(rb),mid+1,r);
return ra;
}
int query(int rt,int l,int r,int val){
if(!rt) return 0;
int mid = (l + r) >> 1;
int res = t[rt].sum;
if(val <= mid) res += query(ls(rt),l,mid,val);
else res += query(rs(rt),mid+1,r,val);
return res;
}
void dfs(int x){
for(int i = head[x];i;i = nxt[i]){
int y = to[i];
dfs(y);
f[x] = merge(f[x],f[y],1,M);
}
int ans1 = query(f[x],1,M,v[x]-1) + 1;//选这个节点,所以去找小于v[u]-1的节点数
int ans2 = query(f[x],1,M,v[x]);//不选这个节点
if(ans1 <= ans2) return;//选了还不如不选,那么就算选了也不是最优解
int l = v[x],r = M,pos = v[x];
//如果这个节点要选,可能子结点中比自己大的节点的可选节点数大于自己
//由于这个节点是+1得到的,那么就要去找到比自己大的节点中可选节点数小于自己的最大的节点
//也就是要找一个最大的区间,使得这个区间中每个点的可选节点数都要小于自己
//然后把这个区间的值+1
while(l <= r){//二分找到最大的区间右端点
int mid = (l + r) >> 1;
if(query(f[x],1,M,mid) < ans1){
l = mid + 1;
pos = mid;
}else r = mid - 1;
}
update(f[x],1,M,v[x],pos);
}
int main(){
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n = in();
for(int i = 1;i <= n;++i){
lsh[i] = v[i] = in();
int x = in();
add(x,i);
}
sort(lsh+1,lsh+n+1);
M = unique(lsh+1,lsh+n+1) - lsh - 1;
for(int i = 1;i <= n;++i)
v[i] = lower_bound(lsh+1,lsh+M+1,v[i]) - lsh;
dfs(1);
printf("%d",query(f[1],1,M,M));//大根堆,搜最大的就好了
return 0;
}