chxT1 不会
T2
题意：给定两棵树，统计总共有多少个点对 $(x,y)$ 满足 $x$ 在 $y$ 的子树中, $n\le 300000$
一开始以为是树形dp，后面假了，因为并不满足 $(x~in~y),(y~in~z) \rightarrow (x~in~z)$，然后仔细想了一下一直卡住是因为时间复杂度是 $O(ans)$ 的，考虑怎么一次性统计多个点对，然后发现 $x~in~y$ 说明 $dfn[x] \in [dfn[y],dfn[y]+siz[y]-1]$ ，然后就是一个二维偏序问题，用个树状数组就行了。
T3
题意：有 $n$ 个点，每个点有能力值和一个权值，能力值互不相同，每次随机挑选两个然后将能力值小的那一个给移除出去，求倒数第二个数的权值的期望
一开始瞎jb乱搞假了，其实看了正解觉得非常简单，一开始大多都是直接算假期望，即使用所有方案的权值之和除以所有方案来计算平均数，实际上还有真期望法，即使用期望来计算期望，这题使用真期望的方法更好。首先考虑一个序列的能够走到最小那个值的概率是多少，简单推出来是 $\frac{1}{{n\choose 2}}$，然后考虑每次从大往小往序列里加元素，考虑插入到第 $i$ 元素，这个元素当前一定是最小的，然后就可以计算出加入这个元素后新的序列以这个元素结尾的对新期望产生的贡献，即 $b[i]\cdot \frac{1}{i\choose 2}$ ，而剩下的部分则是别的大的元素产生的贡献：$(1-\frac{1}{i\choose 2})\cdot E[1 \text{~} (i-1)]$ ，那么就有 $E[1\text{~}i]=b[i]\cdot \frac{1}{i\choose 2}+(1-\frac{1}{i\choose 2})\cdot E[1 \text{~} (i-1)]$ ，而答案就是 $E[n]$