5469: [FJOI2018]领导集团问题

链接

题意：

　　要求在一棵树内选一个子集，满足子集内的任意两个点u,v，如果u是v的祖先，那么u的权值小于等于v。

分析：

　　dp[u][i]表示在u的子树内，最大的数是i的时候，最多选多少点。其中每个i都要和i+1取max，即每个i维护后缀最大值。

　　考虑优化：如果不考虑u的权值，对dp数组从后往前差分，然后得到的一定全是正数，而且此时的差分数组就是所有子节点的差分数组的和（即把每一位上的数字求和）。

　　而合并差分数组是可以做到$O(nlogn)$的，因为只需要在出现的权值的位置+1，所以可以启发式合并。

　　然后加上w[u]后，考虑差分数组发生什么变化，在w[u]处+1，w[u]前面第一个出现的点-1。于是可以set维护。总复杂度$O(nlog^2n)$

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

multiset<int> dp[N];

vector<int> e[N];

int w[N];

void Merge(int u,int v) {

    if (dp[u].size() < dp[v].size()) dp[u].swap(dp[v]);

    for (multiset<int> :: iterator it = dp[v].begin(); it != dp[v].end(); it ++) dp[u].insert(*it);

}

void dfs(int u) {

    for (int sz = e[u].size(), i = ; i < sz; ++i) dfs(e[u][i]), Merge(u, e[u][i]);

    multiset<int> :: iterator it = dp[u].lower_bound(w[u]);

    if (it != dp[u].begin()) it --, dp[u].erase(it);

    dp[u].insert(w[u]);

}

int main() {

    int n = read();

    for (int i = ; i <= n; ++i) w[i] = read();

    for (int i = ; i <= n; ++i) e[read()].push_back(i);

    dfs();

    cout << (int)dp[].size();

    return ;

}