题目链接：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维护一个最大的差值。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll; const int N=1e5+,P=1e5;
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];
ll sum[N],ans,mx; inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
void init(){ed=tot=dfs_idx=,ans=mx=;memset(sum,,sizeof(sum));memset(g,,sizeof(g));}
inline void upmax(ll &a,ll b){if(a<b)a=b;}
//------------------树状数组
inline void add(int x,int c){while(x<=P)sum[x]+=c,x+=x&-x;}
inline ll ask(int x){ll an=;while(x)an+=sum[x],x-=x&-x;return an;}
//------------------主席树
struct node{int l,r,sum;}T[N*]; inline void update(int &x,int y,int pos,int l=,int r=P)
{
T[++tot]=T[y],T[tot].sum++,x=tot;
if(l==r)return;
int m=l+r>>;
if(pos<=m)update(T[x].l,T[y].l,pos,l,m);
else update(T[x].r,T[y].r,pos,m+,r);
} inline int query(int x,int y,int k,int l=,int r=P)
{
if(l==r)return l;
int m=l+r>>,sum=T[T[x].l].sum-T[T[y].l].sum;
if(k<=sum)return query(T[x].l,T[y].l,k,l,m);
else return query(T[x].r,T[y].r,k-sum,m+,r);
} void predfs(int u=)
{
sz[u]=,dfn[u]=++dfs_idx;
update(root[dfn[u]],root[dfn[u]-],A[u]);
for(int i=g[u];i;i=nxt[i])predfs(v[i]),sz[u]+=sz[v[i]];
if(!g[u])mid[u]=A[u],val[u]=P-A[u],ans+=A[u];
else
{
int s=sz[u]+>>;
mid[u]=query(root[dfs_idx],root[dfn[u]-],s);
val[u]=query(root[dfs_idx],root[dfn[u]-],s+)-mid[u];
ans+=mid[u];
}
} void dfs(int u=)
{
add(mid[u],val[u]);
upmax(mx,ask(P)-ask(A[u]-));
for(int i=g[u];i;i=nxt[i])dfs(v[i]);
add(mid[u],-val[u]);
} int main()
{
while(~scanf("%d",&n))
{
init();
F(i,,n)scanf("%d",A+i);
F(i,,n)scanf("%d",&x),adg(x,i);
predfs(),dfs();
printf("%lld\n",ans+mx);
}
return ;
}