给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。 你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。 请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。
思路比较直接 设 \(f[i][j]\) 表示\(i\)为子树的节点中,堆中最大值小于\(j\)的情况下能选的最多点数 转移时就是用一个前缀最大值更新一个后缀 用线段树维护即可,向上推时顺便把线段树合并 区间max直接打一个永久化标记 还要打区间加法标记,下放即可 注意各种地方都要下放,QwQ
#include<bits/stdc++.h> using namespace std; const int N=200005; int n,head[N],nxt[N<<1],to[N<<1],num=0,m,a[N],b[N],cnt=0,rt[N],ans=0; inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;} struct node{ int ls,rs,la,w; }tr[N*24]; inline void pushdown(int x){ int ls=tr[x].ls,rs=tr[x].rs; if(ls)tr[ls].la+=tr[x].la,tr[ls].w=max(tr[x].w,tr[x].la+tr[ls].w); if(rs)tr[rs].la+=tr[x].la,tr[rs].w=max(tr[x].w,tr[x].la+tr[rs].w); tr[x].la=0; } inline void add(int &x,int l,int r,int sa,int se,int t){ if(!x)x=++cnt; if(sa<=l && r<=se){tr[x].w=max(tr[x].w,t);return ;} pushdown(x); int mid=(l+r)>>1; if(se<=mid)add(tr[x].ls,l,mid,sa,se,t); else if(sa>mid)add(tr[x].rs,mid+1,r,sa,se,t); else add(tr[x].ls,l,mid,sa,mid,t),add(tr[x].rs,mid+1,r,mid+1,se,t); } inline int merge(int x,int y){ if(!x||!y)return x+y; pushdown(x);pushdown(y); if(!tr[x].ls) tr[x].ls=tr[y].ls,tr[tr[x].ls].w+=tr[x].w,tr[tr[x].ls].la+=tr[x].w+tr[x].la; else if(!tr[y].ls)tr[tr[x].ls].w+=tr[y].w,tr[tr[x].ls].la+=tr[y].w+tr[y].la; else tr[x].ls=merge(tr[x].ls,tr[y].ls); if(!tr[x].rs) tr[x].rs=tr[y].rs,tr[tr[x].rs].w+=tr[x].w,tr[tr[x].rs].la+=tr[x].w+tr[x].la; else if(!tr[y].rs)tr[tr[x].rs].w+=tr[y].w,tr[tr[x].rs].la+=tr[y].w+tr[y].la; else tr[x].rs=merge(tr[x].rs,tr[y].rs); tr[x].w+=tr[y].w; return x; } inline int qry(int x,int l,int r,int sa){ if(!x || !sa)return 0; if(l==r)return tr[x].w; int mid=(l+r)>>1; pushdown(x); if(sa<=mid)return max(qry(tr[x].ls,l,mid,sa),tr[x].w); return max(qry(tr[x].rs,mid+1,r,sa),tr[x].w); } inline void dfs(int x){ for(int i=head[x];i;i=nxt[i])dfs(to[i]),rt[x]=merge(rt[x],rt[to[i]]); add(rt[x],1,m,a[x],m,qry(rt[x],1,m,a[x]-1)+1); } inline void DFS(int x){ if(!x)return ; ans=max(tr[x].w,ans); pushdown(x); DFS(tr[x].ls);DFS(tr[x].rs); } int main(){ freopen("pp.in","r",stdin); freopen("pp.out","w",stdout); scanf("%d",&n); for(int i=1,x;i<=n;i++){ scanf("%d%d",&a[i],&x); if(x)link(x,i);b[i]=a[i]; } sort(b+1,b+n+1);m=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+m+1,a[i])-b; dfs(1);DFS(rt[1]); cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/Yuzao/p/8439996.html
相关资源：数据结构—成绩单生成器