Problem A
Problem B
考虑第二种优惠，每一个物品如果原价购买了，
那么向可以免费拿的那个物品连一条边（在树上被指向的那个点是父亲）
如果不考虑环的话，考虑树上DP。
设$f[i][0]$表示买掉以$i$为根的子树需要的最小花费，
设$f[i][0]$表示买掉以$i$为根的子树并且$i$这个点是原价购买的最小花费。
那么买掉$i$子树的最小花费和为$f[i][1] - p[i]$，就可以转移了。
分开考虑每个连通块。
每个连通块是一个环的结构。
先用刚才树DP的做法得到每个点的值，然后在环上DP。
具体一点，把环断开来，枚举链头是原价买的还是被链尾打包了。
然后就类似刚才的方法DP下去就可以了。
Problem C
Problem D
Problem E
设$f[i][j]$为以$i$为根的子树所有连通块大小为$j$的权值和。
这是一个可逆的DP。
把一个点加到某个点的儿子集合中去，这个DP比较显然，我只要合并两个数组就可以了。
这样的话把一个点从某个点的儿子集合中剥离出来，也是可以做到的。
操作$0$的话很简单，从这个点到$10$级祖先一个个剥离，然后更新这个点的数组，
然后一个个放回去就可以了。
操作$1$的话，从这个点到$10$级祖先一个个剥离，
然后从这个点的父亲开始一个个放回去（这个点要给别人了）
然后被加的那边也是类似的操作。
操作$2$也就是询问很神奇。首先继续从这个点到$10$级祖先一个个剥离。
这个过程其实也可以看作是把$10$棵树各自分离。
然后询问的时候把当前点想象成根，把他的原来的祖先的数组合并到他那里
这样处理就很方便，然后撤销就可以了。
Problem F
Problem G
Problem H
Problem I
模拟，考虑两条对角线控制的$8$个点，这$8$个点为$1$组，然后讨论下取个最大值就可以了。
Problem J
比赛的话也只能靠做做这种题活命了……
给每个点赋一个比较大的数，如果一个点被操作了$x$次，并且被操作的数都是这个点的权值本身$y$的话。
那么我们可以给他计算一下在他身上操作过的数的和。
最后如果等于$xy$，那么就活着。
那么问题转化成了二维前缀和，就可以做了。
Problem K
首先行和列是可以分开考虑的。
对于每一行，求出这一行的循环节可以是哪些数。
这个哈希搞一下就可以了。
这个循环节跟平时的不太一样，
意思是如果复制无限次后能覆盖当前整行就行。
显然如果一个数可以作为所有行的循环节，那么这个数就可以作为矩阵的长。
那么列这边也是同样的道理。
最后求一下子矩阵最大值的最小值，滑动窗口就行。
原文：https://www.cnblogs.com/cxhscst2/p/9385350.html