[bzoj4919] [Lydsy1706月赛]大根堆

思路

将链上的最长上升子序列问题拓展到树上，dfs一遍，使用线段树合并+标记永久化维护dp数组。

代码

#include  
#include  
#include  
#include  
#define maxn 200020  
#define logn 19  
using namespace std;  
int n,a[maxn],cnt,tmp[maxn];  
inline void get(int &x){  char c=getchar();bool p=0;  while((c<'0'||c>'9')&&c!='-')c=getchar();  if(c=='-')p=1,c=getchar();x=c-'0',c=getchar();  while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();  if(p)x=-x;  
}  
int tot,la[maxn];  
struct edge{  int v,ne;  
}e[maxn];  
inline void add(int u,int v){e[tot].v=v,e[tot].ne=la[u],la[u]=tot++;}  
int rt[maxn];  
struct Segment_Tree{  int mem;  struct node{  int l,r,v;  }t[maxn*logn];  void init(){mem=0;}  inline void update(int &o,int l,int r,int ql,int qr,int v){  if(!o)o=++mem;  if(ql<=l&&r<=qr){t[o].v+=v;return;}  int mid=(l+r)>>1;  if(qr<=mid)update(t[o].l,l,mid,ql,qr,v);  else if(ql>mid)update(t[o].r,mid+1,r,ql,qr,v);  else update(t[o].l,l,mid,ql,qr,v),update(t[o].r,mid+1,r,ql,qr,v);  }  inline int merge(int x,int y){  if(!x||!y)return x+y;  t[x].v+=t[y].v;  t[x].l=merge(t[x].l,t[y].l);  t[x].r=merge(t[x].r,t[y].r);  return x;  }  inline int query(int o,int l,int r,int x){  if(!o||!x)return 0;  int mid=(l+r)>>1;  if(x<=mid)return t[o].v+query(t[o].l,l,mid,x);  else return t[o].v+query(t[o].r,mid+1,r,x);  }  
}tr;  
void init(){  tot=0;get(n);tr.init();  memset(rt,0,sizeof(rt));  memset(la,-1,sizeof(la));  for(int i=1;i<=n;++i){  int fa;get(a[i]);get(fa);  tmp[i]=a[i],add(fa,i);  }  sort(tmp+1,tmp+n+1);  cnt=unique(tmp+1,tmp+n+1)-(tmp+1);  for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+cnt+1,a[i])-tmp;  
}  
inline void dfs(int u){  for(int i=la[u];~i;i=e[i].ne){  int v=e[i].v;dfs(v);  rt[u]=tr.merge(rt[u],rt[v]);  }  int v=tr.query(rt[u],1,cnt,a[u]-1)+1;  if(v<=tr.query(rt[u],1,cnt,a[u]))return;  int l=a[u],r=cnt+1,mid=(l+r)>>1;  while(l<r){  if(tr.query(rt[u],1,cnt,mid)<v)l=mid+1;  else r=mid;  mid=(l+r)>>1;  }  tr.update(rt[u],1,cnt,a[u],l-1,1);  
}  
void solve(){  dfs(1);  printf("%d\n",tr.query(rt[1],1,cnt,cnt));  
}  
int main(){  init();  solve();  return 0;  
}  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！