[Acwing|蓝桥] 3422. 左son右兄弟 树形dp

前言

传送门 :

思路

我们贪心的考虑最优解 , 考虑第 i i i层

我们一定是将具有深度越大的节点 放到 深度小的节点处

例如样例, 考虑将 2 2 2放到 3 , 4 3,4 3,4后面

因此我们考虑 动态规划

状态表示 : f [ u ] f[u] f[u] 以当前 u u u为根节点所能构造出的最大深度

状态计算 : f [ u ] = m a x ( f [ u ] , f [ v ] + n u m [ u ] ) f[u] = max(f[u],f[v]+num[u]) f[u]=max(f[u],f[v]+num[u]) 即考虑将最大的子树放到其他节点的后面

因为根节点的计算 需要使用到 子节点

所以我们考虑 从下到上的 d p dp dp

Mycode

const int N  = 1e5+10;
vector g[N];
int num[N];
int f[N];

void dfs(int u,int fa){
	for(auto j : g[u]){
		if(j!=fa){
			dfs(j,u);
			f[u] = max(f[u],f[j]+num[u]);
		}
	}
}
void solve()
{
	int n;cin>>n;
	for(int i=2;i>x;
		g[x].pb(i);
		num[x]++;
	}
	
	dfs(1,0);
	cout