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
花了一節課大概聽懂了戰神做法，過于弱了。。。