csps模拟测试74

　　T1：贪心，考试一看70分拿了就跑了。

　　之前一道叫做时间机器的题是区间之间的贪心，一一对应不必打二分图，可以进行最优决策后不反悔。

　　T2：神仙DP。

　　我的思路第一步就死了。

　　f[i][j]表示i个点最大深度为j的方案数，然后往里插点emmmm概率成啥，，，好像啥样的树都有。

　　题解是通过一个g[i][j]来转移，代表i个点形成的森林，最大为j，那么这个东西通过枚举第一个树的深度来求，最后给这个森林加一个根就行了。

　　$g[i][j]=\sum \limits_{k=1}^i g[i-k][j]*f[k][j]*tmp[i][k]$tmp代表i个点形成的森林中k个点在一颗树上的概率。

　　T3：首先这是一个区间上的题，如果想优化，从连续一段的询问上考虑。

　　询问需要知道什么，如果在线段树上二分，那么就可以知道要求的是在某个区间上的边数。

　　然后在换个角度考虑，所谓在一个区间上的边，就是儿子父亲都在这个区间内。

　　所以dfs后维护fa数组，做一遍主席树，每次查询l,r内fa也在l,r内的数量就完了。