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内的数量就完了。