bzoj5469 [FJOI2018]领导集团问题

题目描述

一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 $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 \le w_i \le 10^9$​​。

输出格式

输出找到的最大的部门的成员数。

样例输入

6
2 5 1 3 5 4
1
1
2
2
4

样例输出

4

说明

对于 $10\%$ 的数据,$n\le 20$;

对于 $40\%$ 的数据,$n\le 2000$;

对于 $100\%$ 的数据,$n\le 200000$。


分析

首先问题可以转化成,修改树上某些点的点权,使得整棵树满足$w_u\ge w_{fa(u)}$,最大化未被修改的点的个数。

设$f(u,i)$表示点$u$的点权修改为$i$,子树中未被修改的点数最大值:

$$f(u,i)=[w_u=i]+\sum_{v\in son(u)}\max_{j\ge i}f(v,j)$$

也就是把每个子树【dp数组的后缀$max$数组】按位相加,然后再在$w_u$处加一。我们设dp数组的后缀$max$数组为$g(u,i)$。

考虑这个dp是否可以优化。目前的复杂度是$O(n^2)$的,而存储每个点的$dp$数组就需要$O(n^2)$的空间。思考我们是否存储了无用的信息。

首先发现转移时基本都是用$g$数组转移的,$f$其实用处不大,可以不存。转移时,先让$f_u=\sum_{v\in son(u)}g_v$(对应位相加),可以发现此时$g=f$。然后我们要在$f(w_u)$处加一。考虑$g$的变化,设$g(w_u)$前面第一个比它大的位置为$g(t)$,则我们需要把$g(t+1)$到$g(w_u)$都加一。

可以发现如果只做区间加一和按位相加的话,$g$数组肯定有很多段相同的数,并且它是从后往前递增的。这启示我们不去储存$g$数组,而是储存它的从后往前的差分数组$h$,这样就会出现很多$0$,我们只需要存储非$0$的位置就好了。

之前转移的时候把$g(t+1)$到$g(w_u)$都加一,可以看成$h(w_u)++$和$h(t)--$。寻找$g(w_u)$前面第一个更大的数,相当于寻找$h(w_u)$前面第一个非$0$数。$g$数组的按位相加,也可以看成$h$数组的按位相加。

既然转化成了单点修改,可以发现$h$数组非$0$数的个数是$O(n)$的,所以可以用一个map来保存。按位相加时可以启发式合并,找前驱非零数直接lowerbound即可。

复杂度$O(n\log^2 n)$。事实上可以用权值线段树启发式合并代替map,可以做到$O(n\log n)$。

代码

#include <bits/stdc++.h>
using std::map;
using std::pair;
typedef map<int, int>::iterator IT;

const int N = 2e5+50;

struct Graph {
    struct Edge {
        int to, nxt;
    } e[N];
    int top, head[N];

    Graph(): top(0) {
        memset(head, -1, sizeof head);
    }

    void add(int u, int v) {
        e[top] = (Edge){v, head[u]};
        head[u] = top++;
    }
} G;

int n, m;
int fa[N];
int w[N];
int disc[N], dif;
map<int, int> f[N];

void merge(int u, int v) {
    if (f[u].size() < f[v].size())
        std::swap(f[u], f[v]);
    for (IT it = f[v].begin(); it != f[v].end(); it++)
        f[u][it->first] += it->second;
}

void dfs(int u) {
    f[u][w[u]] = 1;
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to;
        dfs(v);
        merge(u, v);
    }
    int pos = w[u] - 1;
    if (f[u].begin()->first > pos)
        return;
    IT it = --f[u].upper_bound(pos);
    if (--(it->second) == 0)
        f[u].erase(it);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        disc[i] = w[i];
    }
    std::sort(disc+1, disc+n+1);
    dif = std::unique(disc+1, disc+n+1) - 1 - disc;
    for (int i = 1; i <= n; i++)
        w[i] = std::lower_bound(disc+1, disc+dif+1, w[i]) - disc;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &fa[i]);
        G.add(fa[i], i);
    }
    dfs(1);
    int ans = 0;
    for (IT it = f[1].begin(); it != f[1].end(); it++)
        ans += it->second;
    printf("%d\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论