转移自老blog

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;