CF815C Karen and Supermarket
一、题目点此看题二、解法首先可以把树建出来，由于价格范围太大，所以把物品个数加进状态中，设dp[u][i][0/1]dp[u][i][0/1]dp[u][i][0/1]为uuu为根的子树内，买了iii件物品，uuu有没有被买（能不能用优惠券）的最小花费，转移相当于一个背包，特别注意能用劵的情况下可以让子树不用劵。咋一看这样做的时间复杂度是O(n3)O(n^3)O(n3)的，考虑一种常用的树上复杂度计算方式，由于没对点只会在lcalcalca处被计算一次，所以时间复杂度是O(n2)O(n^2)O(
