T1 数据恢复 T2 下落的小球 T3 消失的字符串 T4 古老的序列问题
还是困，不过已经可以用脑子思考问题了
T1 数据恢复
没啥明确的算法，可以说是贪心？
考虑部分分，
链的直接扫，
对于菊花的发现只要根节点在第一个，剩下的点位置不重要
那么按照$a/b$排序，扫一遍就行。
这启发我们正解如何考虑祖先和儿子的关系
我们设$v=\frac{a}{b}$，那么还是贪心的选择$v$最小的最优
考虑父子关系
如果当前最优的点的父亲被选，那么直接选他更优
如果当前最优的点的父亲没选，那么选上他的父亲再选他更优
这样就可以使用并查集维护，每次找到$v$最小的点后把他和他父亲合在一起，
$a,b$也合并，然后把新的节点插进可重集内，并删掉原来的两个点。
关于答案的累加，直接在合并的时候累加一个$a_j*b_i,fa[j]=i$即可。
证明：
考虑$fa[j]=i$，设$j$后面的$a$的和为$sum$，设$i,j$合并后的大点叫$k$
原来这一部分的答案为$ans=b_j*sum+b_i*(a_j+sum)$
合并后若要计算答案为$ans=b_k*sum=b_j*sum+b_i*sum$，发现少了一项$b_i*a_j$
所以直接在合并时加这一项，剩下的那些答案也会在合并这个的时候被统计，所以直接加这个是正确的。
View Code
T2 下落的小球
考虑设$siz_i$表示子树大小，$w_i$表示$i$子树内叶子节点的$\sum a$，$r_i=w_i-siz_i$
那么这个$r_i$就是这颗子树可以让他的上面的那一条链掉球的数量。
那么直接对于$r$和$siz$做可重集排列就行。
T3 消失的字符串
咕咕咕，只会$k=0$
T4 古老的序列问题
$n<=2000$预处理前缀和表示从$i$到$j$的$\sum \sum cost(i,j)$
然后每次询问$O(n^2)$
单调不降部分分，$\sum \sum a_l*a_r$，拆柿子预处理前缀和就行
然后不会了
30
花了一节课大概听懂了战神做法，过于弱了。。。