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;

}