bzoj5469 [FJOI2018]领导集团问题

题目描述：

bz

luogu

题解：

相当于树上$LIS$问题。

考虑一维情况下的贪心，我们可以用multiset启发式合并搞。

代码：

#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 200050;
template<typename T>
inline void read(T&x)
{
    T f = 1,c = 0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    x = f*c;
}
int n,w[N],hed[N],cnt;
struct EG
{
    int to,nxt;
}e[N];
void ae(int f,int t)
{
    e[++cnt].to = t;
    e[cnt].nxt = hed[f];
    hed[f] = cnt;
}
multiset<int>s[N];
multiset<int>::iterator it;
void Merge(int x,int y)
{
    if(s[x].size()<s[y].size())swap(s[x],s[y]);
    for(it=s[y].begin();it!=s[y].end();it++)s[x].insert(*it);
}
void dfs(int u)
{
    for(int j=hed[u];j;j=e[j].nxt)dfs(e[j].to),Merge(u,e[j].to);
    s[u].insert(w[u]);
    it = s[u].lower_bound(w[u]);
    if(it!=s[u].begin())s[u].erase(--it);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++)read(w[i]);
    for(int f,i=2;i<=n;i++)
        read(f),ae(f,i);
    dfs(1);printf("%d
",s[1].size());
    return 0;
}