熟练剖分？什么鬼，我没学过啊，然后在经历了一番深入读题之后，发现这就是道概率期望题，果断丢掉，最后骗了15分

回到正题，首先理解一下题意，它要给每个父节点选一个重儿子，然后算整个树中最多能经过多少轻边，最后要求算的是这个树中最多经过多少轻边的期望值，这个好说，就是每种不同的分配重儿子的概率，乘以这种情况下经过最多轻边的边数，那这个概率怎么求呢？显然树上DP

由于他最后是分子乘上分母的逆元，那我们就不设概率，改设方案数，这样的话用方案数处以整棵树的方案数就是我们要的概率，设g[i][0/1][j]表示某个父节点的第i个及其之前的儿子们，最长轻链长度为j的方案数，这个0/1是0代表在这个儿子及其之前还没有选过重儿子，1就代表已经选过重儿子，用f[x][j]表示以x为根的子树中最长轻链长度为j的方案数，我们来考虑一下怎么转移

转移肯定是以DFS为载体，我们假设现在搜到了x的第i个儿子那么,前i-1个儿子中最长轻链长度为j，第i个儿子的最长轻链长度为k，则有(注意区分0和1)

g[i][0][max(j,k+1)]+=g[i-1][0][j]*f[i][k]　　————(1)

g[i][1][max(j,k+1)]+=g[i-1][1][j]*f[i][k]　　————(2)

g[i][1][max(j,k)]+=g[i-1][0][j]*f[i][k]　　    ————(3)

观察一下这三个转移方程，其实很好理解,我们先看第一个式子，当目前到这个儿子都没有出现重儿子时，证明这个儿子是个轻儿子，那么他对他父亲的贡献应该是他自己的轻链长度+1，因为他到他父亲也是一个轻链，关于这个乘，其实很好理解，但是我卡了很久，感谢secret给我举的例子以及itawbm同学的友情出演解决了我的问题，其实不管是j大还是k+1大，因为你算的是方案数，所以不管你较小的的那个数比max小多少，他都构成了我的这个max值，就好比在2，5，8，9中选两个数保证这两个数的最大值为9，那只要你选了9，剩下那个数选谁都无所谓，但他们是不同的方案，所以这个地方是乘

第二，三个式子都是对于当到i时有重儿子说的，因为你不知道是在第i个儿子之前就已经出现了重儿子还是这第i个儿子就是重儿子，所以就要分出来这两种情况，而这两种情况的差别在于第i个儿子对于x的贡献，如果是之前就已经出现了重儿子，那第i个儿子和x之间就是一条轻边，那贡献k就需要+1，如果就是第i个儿子做重儿子，那么他和x之间的连边就不构成贡献

这样的话转移方程就结束了，这道题还可以用滚动数组优化g的空间，然后记录一下每个点的子树深度，来减少k和j的循环

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define maxn 3010 6 #define ll long long 7 using namespace std; 8 const long long mod=1e9+7; 9 int n,root;10 ll ny,ans,tot=1;11 int fa[maxn],deep[maxn];12 ll zz[2][2][maxn],fen[maxn][maxn];13 vector 
          
            son[maxn];14 ll ksm(ll a,ll b)15 {16     ll fan=1;  a=a%mod;17     while(b>0)18     {19         if(b&1)  fan=(fan*a)%mod;20         b=b>>1;  a=(a*a)%mod;21     }22     return fan%mod;23 }24 void dfs(int x)25 {26     if(son[x].size()==0)  {fen[x][0]=1;  return ;}27     for(int i=0;i