E. Hanging Hearts #831 div1+2

Problem - E - Codeforces

题意给你一棵树，给你一个数字，让你自己构造一个排列，使得在每次操作之后，在最后得到的序列最长上升的序列长度是多少

操作：删掉叶节点，如果其父节点的值>这个点的权值，就更新父节点的权值，否则不动

分析：

这题不需要实现构造的这个步骤，还有这个题一看就是树形dp

基于贪心策略：

令为以u为根的子树选还是不选u的这个节点此时的最长的长度

不选： 叶节点是可以自己选的，所以不选这个节点，这个节点所形成的子树，里面的最长上升是可以自己决定的，所以所有的分支相加就可以了

选： 基于贪心的策略，根节点的值必定是这个以这个根为节点的子树里面最小的值。所以形成一种链状的形式，因为另一个分支会更大

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=998244353;
int h[N],ne[N],e[N],idx;
int f[N][2];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u)
{
	f[u][1]=1;
	f[u][0]=0;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		dfs(j);
		f[u][0]+=max(f[j][0],f[j][1]);
		f[u][1]=max(f[u][1],f[j][1]+1); 
	}
}
signed main(){
    //IOS;
    int T;
    T=1;
    //cin>>T;
    while(T--)
    {
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) h[i]=-1;
		for(int i=2;i<=n;i++)
		{
			int x;
			cin>>x;
			add(x,i);
		}
		dfs(1);
		cout<<max(f[1][0],f[1][1])<<"\n";
	}
    return 0;
} 
/* 
令f[u][0/1]为在以u为根的子树中，选不选u的这个节点的最大值
 
*/