AK-dream

【题目描述】
一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点$v_i$,且每个成员都有响应的级别$w_i$。越高层的领导,其级别值$w_i$越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点$v_i$和$v_j$,如果$v_i$是$v_j$的子孙结点,则$w_i \ge w_j$。
编程任务:对于任意对于给定的领导树,计算出领导树中最大的部门结点子集。

【输入格式】
第一行有一个正整数$n$,表示领导树的结点数。接下来的一行中有$n$个整数。第$i$个数表示$w_i$。再接下来的$n - 1$行中,第$i$行有一个整数$v_i$表示$v_i$是$i + 1$的双亲结点。
$n$ 为正整数,$n \le 200000$,$0 < w_i \le 10^9$

【输出格式】
输出找到的最大的部门的成员数。

这题目描述故弄玄虚。。。害我看半天 简单来说就是选出树上一个点集(不一定要相连的点) 满足点集中任意两点$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$
其次 如果$j\le w_u$ 那么有可能$dp[v][j]$里面已经取了权值小于$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;
}

 评论