【题目描述】
【输入格式】
【输出格式】
这题目描述故弄玄虚。。。害我看半天 简单来说就是选出树上一个点集(不一定要相连的点) 满足点集中任意两点$i,j$，如果$i$是$j$的直接祖先，一定有$w_i\le w_j$。
题解 设计一个DP方程$dp[i][j]$表示 在$i$的子树中(这棵树是有根树！)，选择的所有点的权值全部大于等于$j$时 最多选多少个点。
如果要选当前节点$u$那么在子树里选的点的权值就必须全部$\ge w_u$所以转移方程十分显然(并不)，如下：
由于$u$的两个不同儿子的子树中怎么选点是互不影响的 所以在转移到$u$之前我们先把$u$所有儿子的$dp[v][j]$对应的加在一起(就是对于每一个$j$把所有儿子的$dp[?][j]$累加起来)
我们再看看$dp[i][j]$的定义 容易发现对于一个点$x$随着$j$的增大$dp[x][j]$肯定是不断减小的
所以转移方程直接写成$dp[u][j]=dp[v][j]+\triangle$
这个$\triangle$是什么？意思是说如果可以取$u$这个点 那么就是$1$否则为$0$
关于能不能取$u$这个点其实不太好考虑 为什么不好考虑呢？首先 如果你取了$u$那么一定要$j\le w_u$
把所有儿子的$dp$值累加总时间是$O(n^2)$的 这就不太行
发现转移是在树上的 我们可以用线段树合并来操作这个DP转移 具体地说 线段树的每一个叶子的位置上存着$dp[i][j]$
对于儿子的$dp$值累加 直接把所有儿子的线段树合并就行了
然后关于那个$\triangle$肯定是有一段$dp[u][j\sim k]$需要加$1$但是线段树合并不支持区间修改
因为我们刚才提到的那个 “随着$j$的增大$dp[x][j]$肯定是不断减小的” 的性质 我们可以让叶子节点存$dp$值的后缀差分数组 这样每次只用改两个点了
到底哪一段要$+1$？后缀差分数组的第$w_u$项肯定是要$+1$的 然后$-1$的位置则是在 从后缀差分数组$w_u$项往前找第一个大于$0$的位置
如果那个位置大于零了 就意味着在$u$的子树里已经取了一个权值小于$w_u$的点了(请自行理解)
这个位置可以用线段树上二分找到(但是这个二分会显得比较抽搐 蒟蒻调半天调不出来只好去参考标程)
答案就是最终的$dp[1][1]$也就是你把$1$号节点那个差分线段树整个加起来
时间复杂度$O(n\log n)$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include <bits/stdc++.h> using namespace std ;int n, w[200005 ], srt[200005 ], mx, ans;int head[200005 ], pre[400005 ], to[400005 ], sz; bool ok;inline void addedge (int u, int v) pre[++sz] = head[u]; head[u] = sz; to[sz] = v; pre[++sz] = head[v]; head[v] = sz; to[sz] = u; } struct tree { int lc, rc, cnt; } tr[4000005 ]; int rt[200005 ], tot;#define lson tr[ind].lc #define rson tr[ind].rc int merge (int x, int y) if (!x) return y; if (!y) return x; tr[x].lc = merge(tr[x].lc, tr[y].lc); tr[x].rc = merge(tr[x].rc, tr[y].rc); tr[x].cnt += tr[y].cnt; return x; } void update (int &ind, int l, int r, int pos, int v) if (!ind) ind = ++tot; tr[ind].cnt += v; if (l == r) return ; int mid = (l + r) >> 1 ; if (pos <= mid) update(lson, l, mid, pos, v); else update(rson, mid+1 , r, pos, v); } void del (int ind) tr[ind].cnt--; if (tr[rson].cnt) del(rson); else if (tr[lson].cnt) del(lson); } void del (int ind, int l, int r, int pos) if (l == r) return ; int mid = (l + r) >> 1 ; if (pos <= mid) { del(lson, l, mid, pos); } else { del(rson, mid + 1 , r, pos); if (!ok && tr[lson].cnt) { del(lson); ok = 1 ; } } if (ok) tr[ind].cnt--; } void dfs (int x, int fa) for (int i = head[x]; i; i = pre[i]) { if (to[i] == fa) continue ; dfs(to[i], x); rt[x] = merge(rt[x], rt[to[i]]); } update(rt[x], 1 , n, w[x], 1 ); ok = 0 ; del(rt[x], 1 , n, w[x]); } int main () scanf ("%d" , &n); for (int i = 1 ; i <= n; i++) scanf ("%d" , &w[i]), srt[i] = w[i]; sort(srt + 1 , srt + n + 1 ); mx = unique(srt + 1 , srt + n + 1 ) - srt - 1 ; for (int i = 1 ; i <= n; i++) w[i] = lower_bound(srt + 1 , srt + mx + 1 , w[i]) - srt; for (int i = 2 , fa; i <= n; i++) { scanf ("%d" , &fa); addedge(fa, i); } dfs(1 , 0 ); printf ("%d\n" , tr[rt[1 ]].cnt); return 0 ; }
