D2T3签到题可真是IQ Decrease，概率独立没想到然后就20pts滚粗了
注意题目是先对于所有点rand一个权值(w)然后再抽卡。
先考虑给出的关系是一棵外向树的情况。那么我们要求在所有点内，根要被首先抽到，然后对于每一棵子树，每棵子树的根需要在这个子树内第一个被抽到，这就是一个很明显的子问题了。
考虑某一个点(x)在它的子树中第一个被抽到的概率。设(W)表示所有点的(w)之和，(W')表示(x)的子树的(w)之和，(w_x)表示点(x)的权值
那么枚举之前抽到的非当前子树的卡的次数有
(p = frac{w_x}{W} sumlimits_{i=0}^{+infty} (frac{W - W'}{W})^i = frac{w_x}{W'})。
那么概率就只和(w_x)和(W')有关系了，那么一个点的所有子树的概率因而也是独立的。
考虑树形DP。因为一个点的概率和(W')有关，所以考虑将(W')作为一个状态：设(f_{i,j})表示点(i)的子树权值和为(j)方案合法的概率，转移直接用类似背包的方式合并儿子，最后考虑当前点，复杂度是(O(n^2))的。
然后就获得了0分的好成绩
接下来考虑存在反向边的情况。我们可以容斥掉这些边，即选择这些边不存在或者让这些边反向。我们枚举这些边的状态，可以获得一个外向森林，在这个森林上DP可以获得一个(O(2^nn^2))的算法
然后就获得了20分的暴力
考虑优化这一部分。注意到瓶颈是枚举边的状态，考虑将这些边的状态直接在DP中显现。如果要求一条反向边反过来和原来的DP是一样的，否则我们可以认为这一棵子树的大小是(0)，在树形DP的时候同样地转移。在DP的时候额外加上一维边的数量，就有一个(O(n^3))的算法，可以获得(50)分。
将容斥系数算入DP方程中，将反边数量一维压掉就可以获得一个(O(n^2))的算法。