cf511D
2019年8月5日
转移自老blog
flag=1 dp[rt]=max(ct[rt]-ct[son]+dp[son]);
flag=0 dp[rt]=1 , dp[rt]+=dp[son]-1;
cf511D
链接
题意
给你一棵树，每个点上有一个flag,如果flag=0，表示这个点的权值是所有子节点权值中的最小值。如果flag=1，表示这个点的权值是所有子节点权值中的最大值。如果一共有k个叶子节点，我们可以给每一个叶子节点安排一个1-k中的权值，但是每个权值只能使用一次，现在想知道根节点权值的最大值。题解
dp[i]代表在以i为根节点的子树中，i的最大排名flag=1 dp[rt]=max(ct[rt]-ct[son]+dp[son]);
flag=0 dp[rt]=1 , dp[rt]+=dp[son]-1;