首页 > 代码库 > hdu_5788_Level Up(树状数组+主席树)
hdu_5788_Level Up(树状数组+主席树)
题目链接：hdu_5788_Level Up
题意：
有一棵树，n个节点，每个节点有个能力值A[i],mid[i]，mid的值为第i节点的子树的中位数（包括本身），现在让你将其中的一个节点的A值改为1e5,问所有的mid的和最大问多少。
题解：
我们可以知道，如果改变其中一个的A[i]，如果A[i]是比他父亲节点的mid小，那么他父亲的此时的中位数就会向后移一位
比如 1 2 3 4 5，第3个点是第2个点的父亲，如果改变了第二个点的A值，那么此时变成了1 3 4 5 1e5，第二个点的父亲的mid就变成了4，相比之前向后移了一位。
所以我们可以用主席树来支持查询中位数，然后预处理出每个节点的mid的值和mid+1的值。
最后用树状数组+dfs维护一个最大的差值。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef long long ll; 5 6 const int N=1e5+7,P=1e5; 7 int A[N],n,g[N],v[N],nxt[N],ed,x,tot,root[N],dfn[N],dfs_idx,sz[N],mid[N],val[N]; 8 ll sum[N],ans,mx; 9 10 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}11 void init(){ed=tot=dfs_idx=0,ans=mx=0;memset(sum,0,sizeof(sum));memset(g,0,sizeof(g));}12 inline void upmax(ll &a,ll b){if(a<b)a=b;}13 //------------------树状数组14 inline void add(int x,int c){while(x<=P)sum[x]+=c,x+=x&-x;}15 inline ll ask(int x){ll an=0;while(x)an+=sum[x],x-=x&-x;return an;}16 //------------------主席树17 struct node{int l,r,sum;}T[N*30];18 19 inline void update(int &x,int y,int pos,int l=1,int r=P)20 {21 T[++tot]=T[y],T[tot].sum++,x=tot;22 if(l==r)return;23 int m=l+r>>1;24 if(pos<=m)update(T[x].l,T[y].l,pos,l,m);25 else update(T[x].r,T[y].r,pos,m+1,r);26 }27 28 inline int query(int x,int y,int k,int l=1,int r=P)29 {30 if(l==r)return l;31 int m=l+r>>1,sum=T[T[x].l].sum-T[T[y].l].sum;32 if(k<=sum)return query(T[x].l,T[y].l,k,l,m);33 else return query(T[x].r,T[y].r,k-sum,m+1,r);34 }35 36 void predfs(int u=1)37 {38 sz[u]=1,dfn[u]=++dfs_idx;39 update(root[dfn[u]],root[dfn[u]-1],A[u]);40 for(int i=g[u];i;i=nxt[i])predfs(v[i]),sz[u]+=sz[v[i]];41 if(!g[u])mid[u]=A[u],val[u]=P-A[u],ans+=A[u];42 else43 {44 int s=sz[u]+1>>1;45 mid[u]=query(root[dfs_idx],root[dfn[u]-1],s);46 val[u]=query(root[dfs_idx],root[dfn[u]-1],s+1)-mid[u];47 ans+=mid[u];48 }49 }50 51 void dfs(int u=1)52 {53 add(mid[u],val[u]);54 upmax(mx,ask(P)-ask(A[u]-1));55 for(int i=g[u];i;i=nxt[i])dfs(v[i]);56 add(mid[u],-val[u]);57 }58 59 int main()60 {61 while(~scanf("%d",&n))62 {63 init();64 F(i,1,n)scanf("%d",A+i);65 F(i,2,n)scanf("%d",&x),adg(x,i);66 predfs(),dfs();67 printf("%lld\n",ans+mx);68 }69 return 0;70 }
hdu_5788_Level Up(树状数组+主席树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。