是不是每做道线段树进阶都要写个题解。。根本不会写

---

Description

给定一棵n个节点的有根树，编号依次为1到n，其中1号点为根节点。每个点有一个权值v_i。 你需要将这棵树转化成一个大根堆。确切地说，你需要选择尽可能多的节点，满足大根堆的性质：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。 请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。

---

Solution

看起来很像一道DP，实际上也确实要用到DP的思想。

设编号为i的点的子树中最大权值为j的最优方案为fi，j，i的权值为vi

在线段树中维护f，进行标记永久化，不需要进行pushup，在求和时累加路径上的变化量即可。

那么我们就能在对树DFS的过程中进行对f的更新。在每次搜到叶节点后开线段树，回溯时进行线段树合并，并进行对f的维护。

对fi的转移，有取i点和不取i点两种情况。不取i时f最小值为子树中最大权值为v[i]的方案总和，取i时为子树中最大权值为v[i]-1的方案总和数+1。

若不取i的最小值大于取i最大值，则直接return

反之则利用f与v的单调正相关的关系进行二分，找到最优决策点并在线段树中更新即可。

具体看代码

Code：

1 #include
2 #define debug cout<<"wrong"<'9'){
10 if(ch=='-') f=-1;
11 ch=getchar();
12 }
13 while(ch<='9'&&ch>='0'){
14 x=(x<<1)+(x<<3)+(ch^48); 15 ch=getchar(); 16 } 17 return x*f; 18 } 19 inline void add(int a,int b){ 20 to[++num]=b; nex[num]=head[a]; head[a]=num; 21 } 22 void write(int x){ 23 if(x<0) putchar('-'), x=-x; 24 if(x>9) write(x/10);
25 putchar(x%10+'0');
26 }
27 void init(){
28 n=read();
29 for(register int i=1;i<=n;i++){ 30 v[i]=read(); 31 add(read(),i); 32 } 33 int d[NN]; 34 for(register int i=1;i<=num;i++) d[i]=v[i]; 35 sort(d+1,d+1+num); 36 ext=unique(d+1,d+1+num)-d-1; 37 for(register int i=1;i<=num;i++) v[i]=lower_bound(d+1,d+ext+1,v[i])-d; 38 } 39 struct node{ 40 int seg,ls[NN*40],rs[NN*40],num[NN*40]; 41 void insert(int &x,int l,int r,int opl,int opr,int val){ 42 if(!x) x=++seg; 43 if(opl<=l&&opr>=r){ num[x]+=val; return; }
44 int mid=(l+r)>>1;
45 if(opl<=mid) insert(ls[x],l,mid,opl,opr,val); 46 if(opr>mid) insert(rs[x],mid+1,r,opl,opr,val);
47 }
48 void marge(int &x,int y,int l,int r){
49 if(!x||!y){ x=x+y; return; }
50 num[x]+=num[y];
51 int mid=(l+r)>>1;
52 marge(ls[x],ls[y],l,mid);
53 marge(rs[x],rs[y],mid+1,r);
54 }
55 int query(int x,int l,int r,int pos){
56 if(!x) return 0;
57 int mid=(l+r)>>1,p=num[x];
58 if(pos<=mid) return query(ls[x],l,mid,pos)+p; 59 else return query(rs[x],mid+1,r,pos)+p; 60 } 61 }segt; 62 void dfs(int x){ 63 for(register int i=head[x];i;i=nex[i]){ 64 dfs(to[i]); 65 segt.marge(rt[x],rt[to[i]],1,ext); 66 } 67 int ans1=segt.query(rt[x],1,ext,v[x]-1)+1; 68 int ans2=segt.query(rt[x],1,ext,v[x]); 69 if(ans1<=ans2) return; 70 int l=v[x],r=ext,mid,pos=v[x]; 71 while(l<=r){ 72 mid=(l+r)>>1;
73 if(segt.query(rt[x],1,ext,mid)<ans1) l=mid+1, pos=mid;
74 else r=mid-1;
75 }
76 segt.insert(rt[x],1,ext,v[x],pos,1);
77 }
78 int main(){
79 init();
80 dfs(1);
81 write(segt.query(rt[1],1,ext,ext));
82 putchar('\n');
83 return 0;
84 }

Code