P4577 [FJOI2018]领导集团问题

链接

luogu
bzoj
他是个重题
bzoj4919: [Lydsy1706月赛]大根堆
代码改改就过了

思路

求树上的lis，要好好读题目的！！！
类似于一条链子的思路，把大于w[u]的改掉

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,w[N];
multiset<int> f[N];
vector<int> G[N];
void dfs(int u) {
    for(auto v:G[u]) {
        dfs(v);
        if(f[v].size()>f[u].size()) swap(f[v],f[u]);
        for(auto x:f[v]) f[u].insert(x);
    }
    f[u].insert(w[u]);
    multiset<int>::iterator it=f[u].lower_bound(w[u]);
    if(f[u].begin()!=it) f[u].erase(--it);
}
int main() {
    n=read();
    for(int i=1;i<=n;++i) w[i]=read();
    for(int i=2;i<=n;++i) G[read()].push_back(i);
    dfs(1);
    printf("%d\n",f[1].size());
    return 0;
}