题目描述：

给定一棵 $n$ 个节点的有根树，编号依次为 $1$ 到 $n$ ，其中1号点为根节点。每个点有一个权值  $v_i$ 。

你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么 $v_i>v_j$ 。

请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。

算法标签：主席树，启发式合并

思路：

这道题相当于在树上的最长上升子序列，考虑父亲与孩子和同一个父亲的孩子之间对答案的影响。

将权值离散化，在每一个节点建成权值为下标的线段树。

首先考虑父亲与孩子，选中这个孩子的答案可以对于权值大于自己的父亲造成贡献，所以我们在线段树中在 $[val[x]+1,mx]$ 这个区间更新当前答案。

孩子之间没有影响，所以我们直接对应权值的答案相加即可。

以下代码：

#include
      
       #define il inline#define _(d) while(d(isdigit(ch=getchar())))using namespace std;const int N=2e5+5;int n,val[N],rt[N],head[N],ne[N],to[N],cnt,b[N],nt,tot;struct node{    int l,r,num;}t[N*40];il int read(){    int x,f=1;char ch;    _(!)ch=='-'?f=-1:f;x=ch^48;    _()x=(x<<1)+(x<<3)+(ch^48);    return f*x;}il void ins(int x,int y){    ne[++cnt]=head[x];    head[x]=cnt;to[cnt]=y;}il void modify(int &x,int y,int l,int r){    if(!x||!y){x=x+y;return;}    t[x].num+=t[y].num;    if(l==r)return;int mid=(l+r)>>1;    modify(t[x].l,t[y].l,l,mid);    modify(t[x].r,t[y].r,mid+1,r);}il void insert(int &x,int l,int r,int ql,int qr){    if(!x)x=++nt;    if(ql<=l&&r<=qr){t[x].num++;return;}    int mid=(l+r)>>1;    if(ql<=mid)insert(t[x].l,l,mid,ql,qr);    if(mid
       
        >1;    if(pos<=mid)return t[x].num+query(t[x].l,l,mid,pos);    return t[x].num+query(t[x].r,mid+1,r,pos);}il void dfs(int x){    for(int i=head[x];i;i=ne[i]){        dfs(to[i]);        if(t[rt[to[i]]].num>t[rt[x]].num)swap(rt[x],rt[to[i]]);        modify(rt[x],rt[to[i]],1,tot);    }    int res=query(rt[x],1,tot,val[x]-1)+1;    if(query(rt[x],1,tot,val[x])>=res)return;    int l=val[x],r=tot,ret=l;    while(l<=r){        int mid=(l+r)>>1;        if(query(rt[x],1,tot,mid)